Jump to content

  • Log In with Google      Sign In   
  • Create Account


Speeding Up A* Pathfinding Idea


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
14 replies to this topic

#1 Psychopathetica   Members   -  Reputation: 186

Like
0Likes
Like

Posted 07 January 2013 - 11:58 PM

Ok basically I have a solid 2D tile engine where I can make the worlds as huge as I want with zero slowdown, a solid A* pathfinding algorithm, a solid A* pathfollowing method, and a solid game in general. Now comes an issue. Lets say I have a pretty hefty size dungeon and I end up pulling a hundred sprites and they all end up chasing after me throughout the dungeon. This obviously causes some massive slowdown cause they all have to go through the dungeon like a maze. Each node is on each tile. In a sense this could be a bad thing, considering the hundreds upon hundreds of nodes each sprite has to follow. However after staring at the nodes I visually have drawn, I noticed something. Many of the nodes don't even need to be there! The only time a node really needs placed is when a new direction is gonna happen as the sprite travels node to node. Yet I have no clue how I can even code this new idea of mine. If anything, it would be possible to truly pull a hundred sprites with next to no slowdown. I would probably be cutting the number of nodes by 75-90%. Any bright ideas how I could pull this off? Thanks in advance everyone.


Edited by Psychopathetica, 08 January 2013 - 12:05 AM.


Sponsor:

#2 Ashaman73   Crossbones+   -  Reputation: 6982

Like
1Likes
Like

Posted 08 January 2013 - 12:32 AM

Any bright ideas how I could pull this off?

For one you can use multiple level of nodes, kind of level of detail. A single grid is at level 0, the highest detailed node, then you need to introduce more abstract nodes which group nodes of the underlying level. Either automatically (e.g. detect bottlenecks and place a node their) or logical one (main road, kitchen, armory ). This way you can try to navigate longer distances on upper level waypoint nets and go only deeper when the agent actually need to travel between two higher level nodes.

 

The second idea is to group entities and calculate only one path for a group and use some crowd behaviour to keep the group together.

 

And least but not last, you can reverse the search by calculating the shortest ways from the target (player) using e.g. dijkstra. This way you need to only calculate one graph and all entities can use this graph to hunt the player down, no need to calculate any path any longer.



#3 Morphex   Members   -  Reputation: 298

Like
0Likes
Like

Posted 08 January 2013 - 01:19 AM

I have implemented a quadtree A* pathfinding, and it massively speed up the algorithm, so I advise you to do the same. Just create a quadtree representation of your map and use it to generate the A* Paths, you will end up with less  nodes, and in the worse case with the same as you have now. (and you would really have to make on purpose to get the that kind of complexion). Search how AOE II did they parthfinding, I remember reading a article about it that helped me to create my own.


Check out my new blog: Morphexe 


#4 ApochPiQ   Moderators   -  Reputation: 14673

Like
0Likes
Like

Posted 08 January 2013 - 01:23 AM

What you describe is basically Hierarchical A* and is a well-known and often-used optimization for pathing in complex graphs. It's a great variant on plain A* and well-worth learning how to implement.

#5 markr   Crossbones+   -  Reputation: 1653

Like
0Likes
Like

Posted 08 January 2013 - 07:04 AM

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.



#6 slicer4ever   Crossbones+   -  Reputation: 3416

Like
0Likes
Like

Posted 08 January 2013 - 09:36 AM

3 things:

1. how are you sorting your open list? this is generally your bottle neck of alot of A* implementations.

2. re-use already calculated paths(assuming that your units can overlap)

3. see above suggestions.


Check out https://www.facebook.com/LiquidGames for some great games made by me on the Playstation Mobile market.

#7 IADaveMark   Moderators   -  Reputation: 2404

Like
0Likes
Like

Posted 08 January 2013 - 12:57 PM

One solution is, rather than pathfinding for the agents to get to the player. Pathfind for the nodes themselves to get to the player. It's a quick pass to go through and attach the direction that an agent in a node should leave that node. That way, each agent only looks at the information contained in the node they are in and proceeds according to the signpost it finds there. The only decision then is how often and when do you update the signposts. That depends a lot on your level layout, of course, but it beats re-pathing for hundreds of agents that are often using the same route to a target.


Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI

Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

#8 Cornstalks   Crossbones+   -  Reputation: 6974

Like
0Likes
Like

Posted 08 January 2013 - 01:13 PM

One way to speed up A* (and can be used in combination with Heiarchial A*) is Jump Point Search A* (not for the feint of heart!).

 

I did something similar to what I think IADaveMark is suggesting. In school my team and I made a game where you were a marine battling hundreds and hundreds of zerglings. A* was way too slow for the zerglings' AI, so instead we did a Dijkstra flood-fill search (starting from the player's location), linking tiles together back to the player (the benefit is that it only requires one search, regardless of how many units you have). That way, each zergling could query the tile they were on top of to know which tile they should move to next in order to progress to the player. We supplemented this with a flocking algorithm so that the zerglings wouldn't line up single file, but instead would properly bunch up around the player. It worked decently enough even with hundreds of zerglings. With more time it could've been perfected, but I'd suggest this method if you've only got one player and many units trying to get to that one player.


Edited by Cornstalks, 08 January 2013 - 01:23 PM.

[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

#9 Psychopathetica   Members   -  Reputation: 186

Like
0Likes
Like

Posted 09 January 2013 - 12:42 AM

Wow guys thanks for the feedback! Currently though I'm making a game similar to World of Warcraft only in 2D, using the same mechanics. How WoW does their AI is this.

 

1.) If you go near an enemy, or in other words, go within their aggro radius, you pull aggro on the enemy and cause the enemy to come after you.

 

2.) If they are melee they will come towards you and attack you head on, while casters, if you are within line of sight, will cast their spells on you.

 

3.) If you run away from them, they will chase you.

 

4.) Sometimes when the enemys are grouped together, their aggro is tied with one another. So if you pull one, you end up pulling the whole group.

 

5.) If you pull a lot of enemys as you run away, they seem to be all single file with one another, until they reach you, circle around you, then attack. Unless they are casters, and they will attempt to cast once within line of sight of you.

 

These rules hold true in my game. I have given thought to quadtrees, but I'm pretty psyched to see there are faster A* algorithms out there as you guys shown me. As for my idea that I mentioned in the first post that may cut my nodes by a huge chunk, I wanna show you a couple images. These images are not my game, but will give you a visual idea of what I'm talking about. The first image I have shows my current A* in action, each node being in every single tile, being a total of 177 nodes. The second image I have shows only 40 nodes, and is what I wanna be able to code. Being able to only add a node to my list only when a direction change happens. The sprite only needs to go towards these nodes rather than going node to node one tile at a time, doing something very similar as the first image, only without bombarding the list with a ton of nodes. Now when you think about it, this cuts the number of nodes by 77.4%! And if you multiply the number of sprites by a lot, this dramatically boosts the speed of the game.

 

Attached Thumbnails

  • AStar1.png
  • AStar2.png


#10 Olof Hedman   Crossbones+   -  Reputation: 2720

Like
1Likes
Like

Posted 09 January 2013 - 04:45 AM

If you, instead of searching the whole grid, create a graph consisting of every intersection/direction change in your labyrinth, you can run A* on that graph.

You can create that graph as a preprocessing stage when generating the level.

 

You don't really need the direction changes (a node with only 1 entry and 1 exit is a bit pointless, as you've realised with the straights), but if they are not too many and it makes the navigation code easier I don't see the harm in having them.



#11 Psychopathetica   Members   -  Reputation: 186

Like
0Likes
Like

Posted 09 January 2013 - 09:05 AM

But considering that my games dungeons arent exactly labyrinths, more like rooms with openings and/or doors, that wouldnt work too well =(



#12 Olof Hedman   Crossbones+   -  Reputation: 2720

Like
0Likes
Like

Posted 09 January 2013 - 09:17 AM

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.



#13 EWClay   Members   -  Reputation: 659

Like
0Likes
Like

Posted 14 January 2013 - 06:11 AM

<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.

#14 wodinoneeye   Members   -  Reputation: 723

Like
0Likes
Like

Posted 21 January 2013 - 08:22 AM

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.


Edited by wodinoneeye, 21 January 2013 - 08:31 AM.

--------------------------------------------Ratings are Opinion, not Fact

#15 Selenaut   Members   -  Reputation: 102

Like
0Likes
Like

Posted 29 January 2013 - 02:38 PM

Okay... Here's what I would reccommend:

  1. 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.
  2. Calculate the weight of coarser tiles as the sum of the tiles that they're comprised of; continue until you reach the highest level.
  3. Find all entry and exit points at every level of tile to see which ones can be connected.
  4. 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.
  5. 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






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS