When stepping from one tile to another tile and
considering the orientation and obstacles
at the same time, I wonder is it possible to
calculate the true distance between 2 nodes
for cooperative pathfinding (increased difficulty)?

In pinter's article, it just precomputes 10-tiles ahead,

but without precomputing the whole map,

precompute 10-tiles ahead seem meaningless,

now I got a map of 1056 tiles,

if I consider both obstacles and orientations

of each step, will it take a tremendous amount

of time to compute?
Thanks

Partitioning the findCost job into 4 independent threads, I had to do

// if there are 1056 tiles
// 4 - 264 chunks

// t1: tile 1 - 264 -> 1056 tiles -> 278,784 paths * 64 = 17,842,176
// t2: tile 265 - 528 -> 1056 tiles -> 278,784 paths * 64 = 17,842,176
// t3: tile 529 - 793 -> 1056 tiles -> 278,784 paths * 64 = 17,842,176
// t4: tile 793 - 1056 -> 1056 tiles -> 278,784 paths * 64 = 17,842,176

If I had 1056 tiles, I divide the starting positions into 4 chunks,
that is 264 tiles per chunk, then I connect them into the rest of 1056
tiles. Given that I can't push the node into the actual cost table
once it is closed, because the threads are not mutual exclusive.
And adding 64 directions per path, each thread has to do 17,842,176 calculations.
Are there any other foreseeable optimizations for this?
Thanks
Jack

I am not sure what you're trying to do, but it seems to me, you're doing a large amount of path finding just as pre-calculation?

If direction of travel doesn't matter, you'd have 2 paths with each action (from source to target and vice versa).

Also, for each intermediate tile on the path you also know the optimal path to the destination (at least in the outgoing direction).

Did you consider storage requirements for the results? It looks huge to me.

Other than that, I think the best bet is to not do this at all in some way.

Some random ideas:

- Use a worse estimate than real costs. A* will expand a little more than in the optimal case, but it's probably quicker.

- Compute paths on demand, instead of literally everything.

hi there,
is worst estimate the same as true distance when for instance when the agent travels around an obstacle, how can I calculate this value? if there is an obstacle the agent to travel around, the octile distance and manhattan distance differ a great deal with the true heuristics

secondly if I calculate the true distance on demand as each astar would take about several hundred opened node checks, and 64 iterations for neighbour nodes to open, it still takes too long to complete

is worst estimate the same as true distance when for instance when the agent travels around an obstacle, how can I calculate this value? if there is an obstacle the agent to travel around, the octile distance and manhattan distance differ a great deal with the true heuristics

For optimal paths, the estimate may never give a value higher than the true distance. (If you do, you will still get a path, it's just not always optimal then.)

In the best case, the estimate is always equal to the true distance. That makes path-finding trivial. There is no need for A* any more. From any position, you just pick the direction with the largest decrease in estimated distance :)

Obviously, you need to do non-trivial computations in your estimate here, as you already stated. As such, it would be useful, but it's not really feasible in most cases.

Any value less than the true distance will however still result in an optimal path. The more you deviate from the true distance, the less steering you give to the search, which results in getting more nodes examined/visited.

The worst estimate is probably the constant 0. This makes traveling in any direction equally attractive, and as a result, you will sort-of flood-fill (ie breadth-first search) the entire search space from your starting point in every direction, until you hit the end-point. This is equivalent to Dijkstra algorithm.

If you want to get deeper insight into how A* behaves under different conditions, I recommend making an animation from the exploration. It is very illuminating to see how it opens and closes nodes as it is running.

I don't have many ideas how to proceed, unfortunately. Maybe you need to reconsider your goals?

From your first post, you say you want to do cooperative path finding, and need to compute the entire map. That would mean the cooperation could use the entire map, right?

Is that a useful feature to have? (just asking)

Another direction is to have a more abstract path concept, but no idea how to do that :(