Pathfinding with weights and walls

Show off your games, demos and other (playable) creations.
Post Reply
User avatar
darkfrei
Party member
Posts: 1168
Joined: Sat Feb 08, 2020 11:09 pm

Pathfinding with weights and walls

Post by 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.
Attachments
2021-05-06T19_30_35-Untitled.png
2021-05-06T19_30_35-Untitled.png (382.12 KiB) Viewed 10360 times
2021-05-06T19_34_48-Untitled.png
2021-05-06T19_34_48-Untitled.png (413.64 KiB) Viewed 10360 times
pathfinding-one-01.love
(2.16 KiB) Downloaded 256 times
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
dusoft
Party member
Posts: 482
Joined: Fri Nov 08, 2013 12:07 am
Location: Europe usually
Contact:

Re: Pathfinding with weights and walls

Post by dusoft »

Is that slow on purpose?
User avatar
darkfrei
Party member
Posts: 1168
Joined: Sat Feb 08, 2020 11:09 pm

Re: Pathfinding with weights and walls

Post by darkfrei »

dusoft wrote: Thu May 06, 2021 8:50 pm Is that slow on purpose?
Yes, it's too fast for understanding by 60 fps.
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
dusoft
Party member
Posts: 482
Joined: Fri Nov 08, 2013 12:07 am
Location: Europe usually
Contact:

Re: Pathfinding with weights and walls

Post by dusoft »

So how does it compare to A* in terms of speed?
User avatar
tomxp411
Prole
Posts: 29
Joined: Thu Apr 08, 2021 5:41 pm

Re: Pathfinding with weights and walls

Post by tomxp411 »

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.
User avatar
darkfrei
Party member
Posts: 1168
Joined: Sat Feb 08, 2020 11:09 pm

Re: Pathfinding with weights and walls

Post by 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 265 times

Upd: Yes, the version 03 needs just only 674 steps.
2021-05-07T23_04_34-Untitled.png
2021-05-07T23_04_34-Untitled.png (418.21 KiB) Viewed 10238 times
pathfinding-one-03.love
(2.25 KiB) Downloaded 282 times
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Re: Pathfinding with weights and walls

Post by 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?
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
Post Reply

Who is online

Users browsing this forum: No registered users and 16 guests