LÖVE

Hi all!

My try to make a pathfinding (not A*), that can find the best maze solution.

Here are 4 cells:
yellow, that costs 0;
dark yellow, that costs 1;
dark dark yellow, that costs 2;
dark dark dark blue, that costs 3, but not walkable

Straight step costs 0.01;
Side step (or direction changing) costs 0.1.

Is that slow on purpose?

dusoft wrote: ↑Thu May 06, 2021 8:50 pm Is that slow on purpose?

Yes, it's too fast for understanding by 60 fps.

So how does it compare to A* in terms of speed?

dusoft wrote: ↑Fri May 07, 2021 5:43 pm So how does it compare to A* in terms of speed?

I'm interested as well, and I'm going to experiment with this, once I reach the pathfinding portion of my game.

I'm working on something right now that will be a little simpler, in terms of the graph, but I want to implement some non-obvious pathfinding algorithms (kind of like how 3 of the ghosts in Pac-Man didn't actually seek Pac-Man himself, but points around him.)

I usually start with Dijkstra, changing the rules if needed. My guess is that Dijkstra on a graph like this will take around 500-1800 iterations, depending on the number of closed-off cells and the complexity of the final solution... where an A* could take as few as 32 iterations (a straight line) but probably take more like 60-100, based on the number of turns in this example.

Version 02: same as version 01, but fast calculation and it counts steps: 1145 steps for full solution.

Possible optimization for next version: update path optimizations before searching new paths.
Upd: Yes, the version 03 needs just only 674 steps.

Seems useful to me, but, yeesh, 675 steps. Doesn't changing heuristic calculation in A* to include the cost of a tile/ neighbour work?