I have been reading quite a bit in order to make the following choice: which path-finding solution should one implement in a game where the world proceduraly generated, of really large dimensions?
Here is how I see the main solutions and their pros/cons:
1) grid-based path-finding - this is the only option that would not require any pre-processing, which fits well. However, as the world expands, memory used grows exponentially up to insane levels. This can be handled in terms of processing paths, trough solutions such as the Block A* or Subgoal A* algorithms. However, the memory usage is the problem difficult to circumvent;
2) navmesh - this would be lovely to have, due to its precision, fast path calculation and low memory usage. However, it can take an obscene pre-processing time.
3) visibility graph - this option also needs high pre-processing time, although it can be lessened by the use of fast pre-processing algorithms. Then, path calculation is generally fast too. But memory usage can get even more insane than grid-based depending on the configuration of the procedural world.
So, what would be best approach (others not present in this list are also welcome) for such a situation? Are there techniques or tricks that can be used to handle procedural infinite-like worlds?
Suggestions, ideas and references are all welcome.
EDIT:
Just to give more details, one should see the application I am talking about as a very very large office level, where rooms are generated prodecuraly. The algorithm works like the following. First, rooms are placed. Next, walls. Then the doors and later the furniture/obstacles that go in each room. So, the environment can get really huge and with lots of objects, since new rooms are generated once the players approaches the boundary of the already generated area. It means that there will be not large open areas without obstacles.
Answer
Given that the rooms are procedural built, portals created and then populated, I have a couple of ideas.
A* works really well on navigation meshes, and works hierarchically as well. I would consider building a pathfinding system that works at two levels - first, the room by room level, and second within each room, from portal to portal. I think you can do this during generation at an affordable rate. You only need to path from room to room once you enter it, so it's very affordable from a memory/cpu cost.
High level A* can be done by creating a graph of each portal and room - a room is the node, and the 'path' or edge is the portal to another room. The cost of traversal has some options - it can be from the centre point of the room to the centre point of the other room, for example. Or you might want to make specific edges from portal to portal with real distances, which is more useful, I suspect. This let's you do high level pathfinding from room A to room B. Doors can be opened and closed, enabling or disabling specific paths, which is nice for certain types of game. Because it's room/portal based it should be pretty easy and affordable to calculate - just distance calculations and graph book keeping. The great thing about this is it reduces the pathfinding memory costs dramatically in large environments since you are doing only the room-to-room finding.
The harder part will be the low level A* because it should be polygonal navigation mesh. If each room is square, you can start with a polygon. When you place obstacles, subtract the area occupied from the polygon, making holes in it. When it's all finished you'll want to tesselate it into triangles again, building up the graph. I don't think this is as slow as you think. The difficult part is performing the polygon hole cutting, which requires a good amount of book keeping on that kind of stuff, but it is well documented within half-edge structures, and established computer science graphics books. You can also perform this generation lazily, in a background graph, as you don't actual need the A* results of this level until someone is in the room - the high level takes care of basic path planning for you. Someone may never even enter the room in a run, because the high level A* never leads them there.
I know I have glossed over the low level navigation mesh generation, but I think it's one of those things you set your mind to and solve and then it's done. There are a bunch of libraries out there like CGAL (http://www.cgal.org) and others that can do this stuff, but really to get it going fast you might need to write it yourself so you only have the things you need.
Alternatively, you could make each room be a grid, and the obstacles fill up parts of the grid, and then do all the standard grid smoothing algorithms, but I like navmesh data as it is small and fast.
Hope that makes some sense.
No comments:
Post a Comment