Pathfinding in a chunked world

[DarkShroom]

i don't think A* is "the standard" i think it depends on what you're doing

AI is very game specific, anyway to explain, say you had 10 apples, you'd need to do 10 A* searches i image, i could cancel the search within both a "finds nearest apple" or a "apple's too far away"

this limit keeps things okay, so does the map size and design, furthermore just one search is made... so for my purposes i always start with a more robust and less specific technique.

Also if i want a load of units to find the player, i can do the flood fill bit, and use the same flood fill map for all the units (again we where ignorant of direction)... with you A*, you might need to perform 40 searches for 40 units looking for the player

I haven't actually got to this stage, granted, i just leave it simple atm, but when i do i can split the function apart, and add a predicate to it


BUT YES, like i say it depends on the scenario, i won't right A* yet partly from being lazy and partly from it being not what i want from pathfinding (i want the nearest apple/enemy/bunnywabbit shortly)

[KayleMaster]

The another problem with A* is that you can't have multiagent pathfinding, where collision is enabled.
Last time I tried this, it only took a minute for the two agents to go in to an endless loop of trying to pass each other.
So I implemented cooperative pathfinding on low level, and I use A* on the high level (using HPA* to make low and high level graphs dynamically).
I just need to optimize the graph generation, both in performance, and in memory, although the former is more important for me. I could definitely shave off some memory if I use C to store the data instead of Lua. But I don't know if the overhead (if there's any?) will be worth it.
I'll guess I have to see for myself.

[erasio]

First of all. Please edit your comments instead of submitting 3 responses (also called double / triple posting). This behavior is generally frowned upon.

Secondly. If you are looking for specific algorithms. Add all the requirements you have to your post. HPA* and JPS are brilliant solutions if only considering the start post. Vastly superior to flood filling in every way.

Additional conditions can change this.

And thirdly. Some pointers and corrections.

Flood filling maps can not be reused. You can cache them. But since flood filling has a central origin. Only pathfinding from that origin to any point checked is possible. And unless you also generate and cache all paths (which will be 4095 paths in a 64x64 grid) you will need to do a tree search on your resulting flood fill map. Significantly cheaper than most pathfinding algorithms.
But still takes extra time per unit. And a significant amount of ram to cache or generate everything for a larger area.
Or a gigantic amount of ram and no extra time.

A* and variations is the standard for pathfinding in games. For very good reasons. Because it is simply superior. Do keep in mind though that pathfinding is the problem of finding a way from A to B. It does not consider multiple potential destinations.

Also if i want a load of units to find the player, i can do the flood fill bit, and use the same flood fill map for all the units (again we where ignorant of direction)... with you A*, you might need to perform 40 searches for 40 units looking for the player

This is where clusters are powerful. Since you would only need to perform a proper pathfinding in small areas which is very fast with A* or even simpler algorithms. And the larger cluster will have all necessary data contained. Making the pathfinding one layer up even faster.

You can also keep adding cluster layers. One chunk = 64 tiles. One chunk = cluster level 1. 64 clusters = cluster level 2, etc.

Ram efficient storing of a lot of information to make pathfinding super fast. If they are within the same cluster, you know almost immediately if there's a path. If they are not or there is no path. You can know within a few checks the approximativ distance. Exact distance isn't important since they are small enough to not be distinguishable by humans and non absolute perfection is acceptable.

Frankly. I find it highly unlikely that flood fill will be more efficient unless you have a very narrow corridor maze which is the worst scenario for A*. And even then it'd be faster during a single search and only start performing worse if you have a large amount of repeated searches.

In more open areas assuming you have a uniform grid. JPS will be faster in almost every case.

Additionally. Do keep in mind that pathfinding isn't necessary on a per frame basis. How far do your characters move within a second? If it's half a dozen tiles, you don't need to recalculate. The path will still be accurate enough until you get very close to the player. At 60fps. You already saved 59 full pathfinding calculations!

You can allow yourself to do only do pathfinding for like one or two units per frame. Regardless of the algorithm you use. And you should absolutely do that.

The another problem with A* is that you can't have multiagent pathfinding, where collision is enabled.
Last time I tried this, it only took a minute for the two agents to go in to an endless loop of trying to pass each other.
So I implemented cooperative pathfinding on low level, and I use A* on the high level (using HPA* to make low and high level graphs dynamically).
I just need to optimize the graph generation, both in performance, and in memory, although the former is more important for me. I could definitely shave off some memory if I use C to store the data instead of Lua. But I don't know if the overhead (if there's any?) will be worth it.
I'll guess I have to see for myself.

This is commonly solved in path following instead of pathfinding. Take a look at flowfields. (Not 100% sure if that's what you meant)

Edit: Essentially. Units cast a "danger" or "comming through here!" field around them. And you deviate from your intended path based on that. You don't do actual pathfinding. You simply modify the direction of travel based on how many units are "commin' through".

Alternatively yeah. A swarm agent. But that only yields positive results if you have actual cooperation between units and do more than just pathfinding with it.

[KayleMaster]

My game is strictly grid based and units going off the grid may cause some misses in animation/ collision and others.
I've seen that trailer many times
Take a look at this: https://youtu.be/lNXEE5IC0kY?t=31s or this https://www.youtube.com/watch?v=hu9K3pfbklo&t=37s
Basically I add a third dimension to A* - time. Also add another action - wait.
When a unit pathfinds, it says, this tile will be occupied at d+1, then the next, at d+2, and so on. This is a bit more costly on memory - and performance, but it works wonders. There are several problems with it tho, for example, different speed units, and head on collision, but these are all addressed in the article by David Silver - Cooperative Pathfinding.

[DarkShroom]

Flood filling maps can not be reused. You can cache them. But since flood filling has a central origin. Only pathfinding from that origin to any point checked is possible.

er well that is reusing them?!? <confused>.... and er clusters for my apples that are pretty much evenly spaced across the map? i find it amusing when people think they seem to know magically about my usage case scenario... yeah i'm not gonna be finding loading predicates and conditions into A* very easy (this is sarcasm)

depends what you want really, i personally prefer a simple solution that works so i can work on gameplay, and then to investigate optimisation... hey hoe, good luck with your phd