• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Psychopathetica

Speeding Up A* Pathfinding Idea

14 posts in this topic

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
0

Share this post


Link to post
Share on other sites

[quote name='Psychopathetica' timestamp='1357624738' post='5018915']
Any bright ideas how I could pull this off?
[/quote]

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.

1

Share this post


Link to post
Share on other sites

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.

0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites

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.

0

Share this post


Link to post
Share on other sites

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.

0

Share this post


Link to post
Share on other sites

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.

0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

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.

 

0

Share this post


Link to post
Share on other sites

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.

1

Share this post


Link to post
Share on other sites

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

0

Share this post


Link to post
Share on other sites

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.

0

Share this post


Link to post
Share on other sites
<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.
0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

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

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0