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.
Speeding Up A* Pathfinding Idea
[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.
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.
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.
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.
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.
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.
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.
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.
