Pathfinding with weights and walls

[darkfrei]

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.

[dusoft]

Is that slow on purpose?

[darkfrei]

Is that slow on purpose?

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

[dusoft]

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

[tomxp411]

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.

[darkfrei]

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.

pathfinding-one-02.love

(2.21 KiB) Downloaded 308 times

Upd: Yes, the version 03 needs just only 674 steps.

2021-05-07T23_04_34-Untitled.png (418.21 KiB) Viewed 11134 times

pathfinding-one-03.love

(2.25 KiB) Downloaded 324 times

[Gunroar:Cannon()]

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