But considering that my games dungeons arent exactly labyrinths, more like rooms with openings and/or doors, that wouldnt work too well =(
Speeding Up A* Pathfinding Idea
Ok...
My suggestion was really just a special case of an hierarchical A* as have been mentioned earlier. (with the extra twist that you could throw away the lower level representation)
If you have interconnected rooms, a natural higher level A* representation would be each room as one node.
When you enter the room, you can run a detailed A* only navigating through that room to its exit.
Or maybe just avoiding obstacles when they run into them...
Or possibly each door as one node, could simplify navigation code at the cost of more nodes to search.
<blockquote class='ipsBlockquote'data-author="markr" data-cid="5019017" data-time="1357650295"><p>
You can split your dungeon into convex regions (AABBs are popular) and store the adjacent regions for each region. Then your A* algorithm doesn't need to work on small tiles individually, but it can consider each region individually, until it reaches the same region as the destination.</p></blockquote>
This is what I do, but with nodes connecting the regions. If you have two rooms with a door between them, there would be a node in the doorway. Or possibly multiple nodes if the connection is wider than a tile. That way the paths are always accurate.
The hard part is generating the regions, since I start from a tile map. I'll give you the algorithm if you're interested.
You can split your dungeon into convex regions (AABBs are popular) and store the adjacent regions for each region. Then your A* algorithm doesn't need to work on small tiles individually, but it can consider each region individually, until it reaches the same region as the destination.</p></blockquote>
This is what I do, but with nodes connecting the regions. If you have two rooms with a door between them, there would be a node in the doorway. Or possibly multiple nodes if the connection is wider than a tile. That way the paths are always accurate.
The hard part is generating the regions, since I start from a tile map. I'll give you the algorithm if you're interested.
There may be some shortcuts depending on the terrain mechanics (like visibility) and the unit behavior.
If visibility is blocked then its unrealistic for a unit to plan out every step of its path to a distant out of visibility (or rough visibility) target.
Getting called (by other units/alarms??) and moving to a known ralleying point near the target would often be done and then finer detail pathfinding from there. You could have a preprocessed ralley point node map (possibly including precalculated stepwise paths between adjacent ralley points). That would be used when the unit is well out of the proximity of the target.
If there are a group of units (you mention hundreds...) ordered to go after the target, they could even share the path calculation and do a simpler 'conga-line' group move
---
I recall once doing some map analysis to try to build 'zones' on a fine detailed grid map. The map mechanics is important for how you decide what the 'zones' are (I used a group of grid cells that were all visible to each other as well as linear 'tunnel' segments that would also be defined as 'zones'. The set of zones was then used for hierarchical pathing to get units close enough to start using fine grid cell pathfinding.
---
Depending on the game, you may not even have to have units alwayson the fine terrain grid and instead move them in an abstract way (zone to zone / high level node to high level node)- at least until it was possible for the player/opposing units to see them ---- then they would be 'realized' on the fine grid.for normal interactions/movement.
------------------------
Oh and if not previously mentioned if you have more open terrain (rooms connected by doors/tunnels) there has been game talk for quite a while about 'portals' - how to find the interface points between zones (often used more for culling out non-visible renderings for terrain/objects in terrain, but may be applicable to (pre)processing sets of 'zones' fro high level movement/pathing.
Okay... Here's what I would reccommend:
- As previous posters have stated, use a multi-level A* algorithm. This means that you take groups of tiles and clump them together to make larger (and thus coarser) tiles that are easier to calculate. You can do this to as many levels as you like, but don't go to crazy.
- Calculate the weight of coarser tiles as the sum of the tiles that they're comprised of; continue until you reach the highest level.
- Find all entry and exit points at every level of tile to see which ones can be connected.
- Path at the highest level which areas you would move through to get to your desired location; then work your way down through the next level, pathing only the current area that the object to pathfind is in. For example, if you have a 16x16 grid, and that is made up of a higher level comprising of a 2x2 grid, only path within the tile on the 2x2 grid you're currently in.
- As soon as the pathfinding object makes their way to another section, restart the pathfinding process of steps 2-4.
This is basically hierarchical A* pathfinding, as many before me have suggested. It's like level of detail, except for pathfinding. :D
Selenaut
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
