Jump to content
  • Advertisement


  • Content Count

  • Joined

  • Last visited

Community Reputation

1486 Excellent

About Telanor

  • Rank
  1. Microsoft, but the physics library already puts enough pressure on the GC to cause occasional pauses, so I try to keep the GC pressure to a minimum where possible. I admit I'm not hugely familiar with the inner workings of the GC, so maybe pressure from short lived objects doesn't matter, but it can't hurt to try to keep it to minimum
  2. After looking through my code I found that I'm not actually doing any addition/removal of components after the initial setup phase, so perhaps I don't need to allow that. I suppose if I did need to allow that, I could pass a lambda function to a ModifyEntity function which the main thread could run at an appropriate time. The function composition is a good idea Sean, shame I didn't set it up that way from the start. Refactoring that is probably going to be quite a pain, more-so because I'm using c# and lambda functions that use capture end up causing allocations, so I'll have to rearrange things to avoid any capturing. I think this'll probably solve the issue though, so thanks for the input guys.
  3. I suppose that would solve the issue during creation time. There'd still have to be an extra call at the end of creating the entity but at least forgetting that would just result in a useless entity rather than a crashing bug, so that's a plus. What about entity modification though? Suppose I want to add a component to an entity after it's already in the world.
  4. I've run into an issue where I'm now creating entities on a different thread than the one that handles sending out entity network updates, which leads to concurrency issues, and I'm not sure what direction to take to fix it. Previously only the main thread ever created entities and it was also the thread that handled sending the updates out. But now the terrain generation is creating entities (trees, in this case) and the terrain generation runs on separate threads. What happens is that the update system tries to enumerate the components of the entity while the entity is still being constructed. I'm using an entity-component system by the way. I could set up a system of locking an entity while it's being created/modified, but since creating an entity isn't a 1 step process, every place in the code where "new Entity" appears (meaning every entity "class"), I'd have to throw in some kind of a "entity.StartUpdate/EndUpdate" pair. If anyone ever forgets to do that... well that's an ugly bug just waiting to happen. I'd prefer a more centralized solution that isn't so easy to screw up. The other option I see is to require entity creation only occur on the main thread. I'm not sure if a restriction like that is a good idea or not. I couldn't find anything useful on google, so I've no idea what the usual design is for such a system.
  5. Telanor

    Pathfinding for large units

    So I fiddled around with the code a bit, made some of the supporting code a bit more efficient. The time is down to about 15s now. Not exactly sure what I changed that made such a big difference, since I got nothing useful out of the profiler and I had to change a lot of things all at once. In any case, the storage requirements are still an issue if I need to store multiple edge values for each block. Using a dictionary to store only non-zero values doesn't help in the least bit since there end up being around 90k entries and apparently each entry costs around 20 bytes. I suppose the next thing I could try is to compute it on the fly and store only a small subset.
  6. Telanor

    Pathfinding for large units

    The directions variable is just a small array of 8 Vector3 offsets. The casting is actually going to happen no matter what because C# doesn't support addition of bytes. It always casts them up to an int32. I'll try replacing the Math.Min call with an if statement though and maybe see if I can do something about the index calculations.
  7. Telanor

    Pathfinding for large units

    Yea, something like that. Its something I'll have to look into again at some point. Interesting. But when building a path from that, wouldn't the path for large units end up being placed along the right most wall, rather than through the middle? The large NPCs wouldn't be able to reach the waypoints if they're all up against the wall like that. Also since my map is essentially infinite, the top and left edges will all be 0/1 for each subdivision (regions as I call them) which would prevent large units from moving along region boundaries. Actually now that I think about it, my implementation of Apoch's suggestion probably has that same issue... I'm not sure how to deal with that.
  8. Telanor

    Pathfinding for large units

    I'm not sure if you're suggesting I compute it as needed and save the results, or if it should still be precomputed. If it is precomputed, its quite a bit of data to store.   I'm not using SIMD because C# doesn't (yet) support it . I'm not sure how I'd know where large empty volumes are without an octree. You can take a look at my code if you like, maybe I'm doing something terribly inefficiently. private static void BuildPathingData(object o) { var region = (Region) o; var sw = System.Diagnostics.Stopwatch.StartNew(); if(region.RegionState != Region.States.Loaded) return; for(var i = 0; i < Region.SizeX * Region.SizeY * Region.SizeZ; i++) { var type = region[i]; if(BlockInformation.IsWalkable(type)) region.PathingInfo[i] = 1; else region.PathingInfo[i] = 0; } for(var i = 0; i < MaxUnitSize; i++) { for(var index = 0; index < Region.SizeX * Region.SizeY * Region.SizeZ; index++) { var value = region.PathingInfo[index]; if(value > 0 && value < MaxUnitSize) { byte smallest = MaxUnitSize; var index3D = new RegionIndex(index); var pos = region.GetVectorPosition(index3D); foreach(var direction in directions) { var neighborPos = pos + direction; var r = new RegionPosition(neighborPos, region.World); var pathValue = r.SelectedRegion.PathingInfo[r.Index]; if(pathValue < smallest) smallest = pathValue; } region.PathingInfo[index] = (byte) Math.Min(smallest + 1, MaxUnitSize); } } } sw.Stop(); Core.Log("Path building took {0}", sw.Elapsed.TotalMilliseconds); } RegionIndex and RegionPosition are both structs, so neither of those 'new's are actually allocating anything.
  9. Telanor

    Pathfinding for large units

    No it's just stored in an array.  We tried using an octree before but ran into problems.  I forget what the issue was.  Earthmark made a post on here a while ago about it but we never did get it working right
  10. Telanor

    Pathfinding for large units

    Well the regions are 32x128x32 voxels, and there's 400 regions loaded around the player.  Each voxel needs to look at 8 neighboring voxels when computing its value.  And it does that 5 times, plus the initial seeding of 1/0s.  So that's about 2.1 billion checks it has to do.  Also I ran it on background threads set to low priority so it wouldn't slow down the main loading threads, so that contributed to some of the slow down. I guess I misunderstood you.  I went and took a look at some pathfinding articles and I think I understand what your referring to with the edges now.  I guess normally you'd build a graph with all the edges between the nodes and their weight values.  Thing is, I don't have that in my implementation.  I have a large, 3d array of voxel 'type ids' and the pathfinding searches through that to build a path.  It calculates the weights and determines what is and isn't walkable on the fly.  The voxel array alone takes up about 200MB for a single player.  If I were to make a graph storing the radius values for the 4 connections of each node, that'd be another 200MB.  It might be fine for 1 player, but if you have 10 players all spread out in different areas, now you're looking at something like 4GB of ram usage just for those 2 sets of data. So I'm not sure it's a feasible solution given the storage requirements.
  11. Telanor

    Pathfinding for large units

    Well I gave it a try, and it ends up taking around 4 minutes to compute for the initially loaded area for N = 5.  Not the best, but not terrible either.  I'm not sure how I'm supposed to use the data though.  For example, an area like this:  0 1 2 2 1 0 could fit up to a 2 radius unit, but the waypoint has to be placed between the 2 voxels.  With an odd number of spaces, you get: 0 1 2 3 2 1 0 which can fit up to a 2.5 radius unit (not 3 as the number indicates) and the waypoint would be in the middle.
  12. Telanor

    Pathfinding for large units

    So if I'm following you correctly, I'd store an extra set of data for each voxel that is basically a measure of how far away it is from the nearest impassable voxel. I suppose if I only search horizontally when computing that number (since my units aren't always going to be cube shaped), the pathfinding can do a simpler vertical search based on the unit's height. One thing I don't understand is this step: "For each cell with a value >= 1, look at its neighbors. Take the lowest adjacent clearance score, add 1, update that cell". In order for that to work, it seems like you'd have to process things by starting at the voxels marked 0 and moving outwards. In other words, if you had this: 0 1 1 1 1 1 0, moving from left to right, you'd end up with: 0 & 1 -> select 0, store 1 -> 0 1 1 1 1 1 0 1 & 1 -> select 1, store 2 -> 0 1 2 1 1 1 0 2 & 1 -> select 1, store 2 -> 0 1 2 2 1 1 0   <- should have been 3 2 & 1 -> select 1, store 2 -> 0 1 2 2 2 1 0 2 & 0 -> select 0, store 1 -> 0 1 2 2 2 1 0   The only way I can think of to fix that is to do N passes through the entire set of voxel data, which could take a significant amount of time.   Edit: Actually, having re-read your post, that's exactly what your suggesting.  I guess I can give that a try, but it seems like it would take a while to compute that for the several million voxels that get loaded.
  13. I'm not entirely sure if this is the right section for this, but here's my problem: I have a 3D voxel world, similar to minecraft, and I'm using A* to do pathfinding for the NPCs. Since the world is laid out in a grid of blocks, I use that same grid for the pathfinding nodes. When the AI follows the path, for units wider than a single grid unit, it gets stuck a lot of times. The first issue it has is when it comes to a ledge that it needs to drop down from, as shown in my crappy drawing: [attachment=22189:diagram.png] The AI gets to the node above the ledge, but can't fall down to the next 3 nodes without moving forwards more. The other issue is things like doorways, where its physically impossible for the unit to go through due to the size. It would need the pathfinder to path around and find another, larger, opening. I've tried a bit to make the A* pathfinding work for larger units but the code quickly became a mess and each node check started to require checking a good 15 or so surrounding nodes. Is this the right way to go about it or is there a better solution? Keep in mind its a dynamic world, so precomputed solutions won't work.
  14. Telanor

    Client loading entities

    I kind of figured that would be the answer but wanted to check anyway.  I found this article that seems to go over the topic nicely, thanks to that search term, though I'm not sure why it claims to be an O(1) algorithm.
  15. Suppose you have a large, seamless transition world that's not all kept loaded in memory at the same time. When a player enters a previously unloaded region, the server loads it up and then can easily send out the data to any players nearby upon completion. But how do you deal with players that move into that area after it's already loaded up. They need to have the data sent to them saying what to load and where. And you don't want to waste network bandwidth by constantly sending everyone "create X entity" messages when they already have those entities loaded. So what's the solution to this?
  • 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!