Jump to content
  • Advertisement

3dmodelerguy

Member
  • Content Count

    1139
  • Joined

  • Last visited

Community Reputation

169 Neutral

About 3dmodelerguy

  • Rank
    Contributor

Personal Information

  • Role
    Programmer
  • Interests
    Programming

Recent Profile Visitors

The recent visitors block is disabled and is not being shown to other users.

  1. 3dmodelerguy

    Is my room detection algorithm optimal?

    Thanks for the input, let me address some of the points that I can. About using `continue;`, that might not be common but I generall try to reduce code indention by returning early instead of doing if / else and in loops I do basically the same thing, just continue early. I have found it easier to read code the less indents I have but that is just me. The reason I am setting `RoomIndex` in 2 different locations is because if I don't do it the second time, when I get adjacent tiles for the first set of adjacent tiles, those might include adjacent tiles for the previous tile I got adjacent tiles for and I need to make sure I do not try to process those tiles multiple times (without that second setting of `RoomIndex`, my game hangs for a really long time, so long that I just kill it). Maybe I can change how I get the adjacent tiles so that wont happen but that seems like it would be more complicated (at least for me with my lack of deep knowledge in algorithms / math of that kind) and wanted to avoid that if possible. It does seem like @a light breeze was right about the `tilesToFloodFill.Remove()` that was causing most of my performance issues. While I could use `RemoveAt()` for one of the locations, the other location would not be as easy, I would have to `FindIndex()` which I figure would be just as bad as `Remove()`. Looking at the code again and I realized that I really did not need a `List` and instead could use a `HashSet` since I don't care about ordering or anything else a `List` can do that a `HashSet` can't, I just need a collection to make sure all tiles that should be processed are. When I switch to using a HashSet the time drop drom ~6000ms to about ~100ms. While is what not the main cause, @a light breeze and @Zakwayda were also right that the creation of the a new list for adjacent tiles each time caused a little extra overhead too so instead I made that method take a ref that was passed in to the method for the `List` that way I created it once and just cleared it each loop which took it down further to ~80ms. While there might be other things I can do to improve that time, I think I got it down to a level that I am more than happy and will save further optimization until and if I really need them. Thanks for the insight.
  2. So I have the following method to generate rooms using what I assume is a flood fill algorithm: private void SetupRooms() { SimpleTimer t = new SimpleTimer(); List<Vector2> tilesToFloodFill = new List<Vector2>(); // first figure out which tiles need to be flood filled for (int x = 0; x < _worldWidth; x++) { for (int y = 0; y < _worldHeight; y++) { if (_hasColliders[x, y]) { _tiles[x, y].RoomIndex = WorldRoom.NO_ROOM_VALUE; continue; } tilesToFloodFill.Add(new Vector2(x, y)); } } t.LogRunningTimeMilliseconds($"room flood fill first pass: "); t.ResetStart(); Queue<Vector2> tilesToCheckAdjacentFor = new Queue<Vector2>(); int currentRoomIndex = 0; int tilesProcessed = 0; while (tilesToFloodFill.Count > 0) { tilesToCheckAdjacentFor.Enqueue(tilesToFloodFill[0]); tilesToFloodFill.Remove(tilesToFloodFill[0]); while (tilesToCheckAdjacentFor.Count > 0) { tilesProcessed++; Vector2 tileToCheck = tilesToCheckAdjacentFor.Dequeue(); List<Vector2> adjacentTiles = GetAdjacentTilePositions(tileToCheck); _tiles[(int) tileToCheck.x, (int) tileToCheck.y].RoomIndex = currentRoomIndex; for (int i = 0; i < adjacentTiles.Count; i++) { if ( _tiles[(int) adjacentTiles[i].x, (int) adjacentTiles[i].y].RoomIndex != WorldRoom.UNASSIGNED_ROOM_VALUE ) { continue; } tilesToCheckAdjacentFor.Enqueue(adjacentTiles[i]); tilesToFloodFill.Remove(adjacentTiles[i]); _tiles[(int) adjacentTiles[i].x, (int) adjacentTiles[i].y].RoomIndex = currentRoomIndex; } } _worldRooms.Add(new WorldRoom()); // current room should be filled, clean up for next room currentRoomIndex++; } t.LogRunningTimeMilliseconds($"room flood fill (tiles processed: {tilesProcessed}): "); Debug.Log($"total rooms: {currentRoomIndex}"); } The general timing for this is: room flood fill first pass: : 1.8787ms room flood fill (tiles processed: 58463): : 6069.9302ms While I only expect to have to run this algorithm on the entire map on the initial load of the map (and maybe a few special cases) I am still wondering if there is any way to optimize it to take less than 6 seconds to do it (I would ideally like to have maps 2 - 4 times bigger than the one I am currently testing on so I imagine it would be at 2 - 4 times slower on those maps). Are there any optimization I can make here (including using a different algorithm) to optimize this process?
  3. I figured out my issue in understanding what he was doing in the video. I missed the fact that he was using also using the 1 tile outside of the region in determining the link data in which case links in 2 side by side regions will always match, after understanding that (and a lot of trial and error debugging) I got the region code to work how I was wanting.
  4. 3dmodelerguy

    Doing AStar Pathing Finding In Threads

    I will keep the idea of having each thread has access to its own grid to be able to parallelize the path finding if needed however the solution of locking the grid seems to be work well for me now so just going to stick with that until it becomes a problem. The more common use case it going to be having many seekers and targets at the same time so I think I would rather stick with one path finding solution if possible instead of trying to implement different algorithms for different use case (seems like that could get really complicated) and A* seems like the more generally use path finding solution (and the first one that I found a good video explaining the algorithm that actually made sense to me).
  5. @JohnnyCode I want to avoid checking each tile individually as if the item being looked for is really far away, that is not going to perform so well the larger the maps get and I do want to be able to support a relatively large map. To try to better explain the problem I am trying to solve, take this image as an example: The orange-ish outline is the active region and the gray-ish outlines are the connected regions (arrow are the edges where they connect). Building out the regions is something I already have working (basically I split the map into 12 x 12 regions and then for each region, I do a flood fill so that if there are non-connected sections in the region, those are then broken out as separate regions. What I am trying to figure out is what is the most efficient way of knowing what regions connect to other regions. The section of the video I linked, he talked about how he would hash certain pieces of data together (mainly the edges direction, length, starting x and y) and that would allowed him to easily connect regions and allow for the ability to only need to modify specific regions as they changed and not rebuild the entire map when something changed. That is the part I am completely lost on as I have not idea how the hash of that data can be use to determine region connectivity.
  6. 3dmodelerguy

    Doing AStar Pathing Finding In Threads

    @markypooch Unfortunately having the grid be uniform in cost is not something I can do so it would seem like jump point searching would not be practical. Moving this code into its own thread does not seem like it is causing any measurable performance difference from my crude benchmarking as the code that is running is the same as if it was running in the main thread (expect that it is running within a lock block so there is the minor overhead for that). The real benefit that I was looking for in the the main Unity thread is no longer being blocked while the A* is running so even if I have a spike where I need to but path for like 30, 40, 50 agents (which might happen), the game itself will not lag (maybe the paths for those agent wont be immediate but that is much better than the game lagging while the path are being generated).
  7. So I am trying to build a game with a 2d world similar to RimWorld / Prison Architect / SimAirport / etc. and trying to figure out a way to split up the world to make it easier to query for close by objects and such. The game will have a lot of items on the map and the map will be a relatively big shooting for a minimum of 200 x 200 but would like to be able to go so sizes like 300 x 300 or 350 x 350 if possible so if I want to find the closest X and there 500 X on the map, looping through each X and checking the distance and figuring out the closest one will not scale (I've tried). Currently I have a region system that breaks the map up into 12 x 12 sections and each region keeps a list of items that need to be queries, This makes it quick to just first search the regions closest to see if they have the item being looked for and then it a region does, just checking the items in that region for distance instead of them all. This system was inspired by the video the RimWorld's developer put on basically describing this however there is one issue I am running into. Right now my regions are fixed and if there is a structure that is fully enclosed, my region system still thinks the enclosed area is part of that region and accessible even if it is not. In the video he shows that if there are region that are cut up by impassible tiles, those regions would be split up and the 2 would not think they are connected at the point. While I have an idea on how to split the regions up by impassible tiles, how to properly makes sure the regions are not connected is a little harder for me to understand. At this point of the video: https://www.youtube.com/watch?v=RMBQn_sg7DA&feature=youtu.be&t=1361 He describes a system where each region store some pieces of information about each link (direction, length, starting x, and starting y) as an int using different bits for those pieces of information and while I think I have figured out how to do that, what I don't understand is how I can use that data to efficiently figure out which regions are linked without having to make sure the data structure is in a specific order so that those regions can be removed / add in any order. This is the code I have so far: https://repl.it/repls/TrainedCalculatingIntelligence Is there a way with that data to be able to determine that link 1 / 2 / 3 are connected but link 4 is not?
  8. 3dmodelerguy

    Doing AStar Pathing Finding In Threads

    @Zakwayda This is the specific video on multi-threading:
  9. 3dmodelerguy

    Doing AStar Pathing Finding In Threads

    As far as if I am sure the grid is directly being modified with path finding state, I am pretty sure that it is (if I understand how C# deals with values properly). While I did write the code I am using myself, the linked here is from the author and this code for the most part is the same. When path finding, these are the lines that get the nodes from the main grid: https://github.com/SebLague/Pathfinding/blob/master/Episode 10 - threading/Assets/Scripts/Pathfinding.cs#L24-L25 https://github.com/SebLague/Pathfinding/blob/master/Episode 10 - threading/Assets/Scripts/Pathfinding.cs#L45 If you take a look at those methods, these are what they are doing: https://github.com/SebLague/Pathfinding/blob/master/Episode 10 - threading/Assets/Scripts/Grid.cs#L123-L153 Based on the code, I believe those method are returning references in which case when they are modified here: https://github.com/SebLague/Pathfinding/blob/master/Episode 10 - threading/Assets/Scripts/Pathfinding.cs#L52-L54 The instances being stored in the grid are being updated. As far at the multi-threading, he does go into it however it does not work for me like it does for him. I deviated a little in the implementation but nothing that I would think would cause an issue with multi-threading (mostly changes so that the implementation only focuses on 2D support, not worrying about any 3D stuff). I was able to prevent the issue by using locks in the path finding code and while that does provide the benefit of having the path finding code run outside the main Unity thread, the paths are still being generated serially in those threads which is not ideal so trying to see how I might be able to get the path finding processes to also run in parallel or each other.
  10. So I was following this tutorial series: While this working well in the beginning, when I attempted to implement thread, is broken. The code for generating the path would never finish. When I only had 1 seeker and 1 target, it worked fine, but having 2 or more seekers target the same target and it breaks. I tested it with 2 seeker following 2 different target where the paths would not cross and everything worked fine. The only thing that makes sense is that in the threads that are running at the same time are trying to modify the same node in the grid causing bad things. I though it was weird that the path generation was modifying the node that the main grid stores directly, if this common? How would I be able top handle generating multiple paths at the same time using thread for this kind of setup?
  11. I am not talking about releasing into early access or anything like that, I am talking about putting up a free tech demo that is playable in a WebGL release of some sorts. Not really sure what you mean by this.
  12. Is it worthwhile to release a playable tech demo that is in a really early / rough state? By tech demo I mean that I just have a few core mechanics implemented at a basic level that gives me something I could call "playable" (using that term very loosely). for example, in my current top down 2D RPG alone the line of Zelda currently has: basic game loop (start menu with button -> button loads game -> you die -> start menu) 2 world sections built with ability to transition between them basic player controller with movement and combat (melee and ranged support) enemy spawning with basic AI for wandering, following, and attacking a few different ways (melee, ranged, charge attack) inventory system with enemies able to drop randomized loot basic crafting system very basic animation for different states (as in rotating sprites and color animation to show different states) basic music and sound effects Some of what I hear is that releasing a tech demo too early really is not going to give any good feedback because there might not be enough to give feedback on but I heard other opinions where you should get people to play your game even if it is just cubes moving around (and even as I play test this, things are coming to mind a lot quicker than just trying to think of them). What are peoples opinion (and maybe more importantly experience) with releasing tech demos for public consumption when it is in a really rough and basic state?
  13. @IADaveMark If you were to put up a C# utility based AI system on the Unity assets store I would probably get it as I am sure it would be infinitely better than anything I will come up with. There are a few solutions I have found on the assets store however they all seem to be either pretty old or highly designed around using the Unity editor to generate the AI (I have a requirement that I need to be able to build the AI at runtime based on json data files).
  14. So I am attempting to implement a basic start to a utility based AI in Unity and I have something that seems to be working and wanted to get any impressions people might have about how I have it setup, all the relevant code can be found here that implements a basic AI for moving and being idle: https://gist.github.com/ryanzec/26fa3558d539f782a2101c241081622c
  15. So I am working on a 2D game in Unity that would probably be best described as a top down game similar to Starbound / Terraria with a much heavier focus on combat and character progress and less on the exploration / building. Up until now my enemy controller has been very basic with just inline code that does basic checking around itself for the player, chasing the player if in a certain range, attacking the player in a certain range, and so on. I am now trying to have more behaviors that the enemy can have and having all this inline in the enemy controller is getting a bit hard to manage and make more modular to make enemies with different behavior easily. For example I would want to have a number of different actions an enemy can do: Roam when a target is not in range (whether the be the player or another NPC) Roam when a target is not in line of sight Chase target when it enters within the enemies range Chase target when it enters the line of sight on the enemy Range attack target when it is in certain range of the enemy Melee attack target when it is in certain range of the enemy Teleport to a random location within a certain range when the target gets close enough to the enemy Perform seal heal when enemy's health gets too low Run away when the enemy's health gets too low Not all enemies will have all these possible actions so I want to be able to as easily as possible add and remove these action for enemies and just as easily add new actions to the pool of available actions. I am trying to figure out the best way to handle this kinda of behavior. Finite State Machines seem to be the most common thing I see suggested but was wondering if there might be something else I should be looking into. Also looking for learning resource for whatever solution I end up going with (ideally something in video form and even better if it is focused on a C# implementation). Any help with this would be awesome, Thanks.
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!