Dijkstra Maps implementation rotLove

General discussion about LÖVE, Lua, game development, puns, and unicorns.
Post Reply
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Dijkstra Maps implementation rotLove

Post by Gunroar:Cannon() »

I'm trying to use rotLove's dijkstra map but I don't understand how to use it like brogue here. The map looks like it uses x and y's not an array, and I don't even know how it works in finding a path the example. Iterate through all the values after calling compute? Could someone please elaborate :). Also, how can I edit it to do all that stuff listed down in the previous link?

Edit: I read somewhere A* is an improvement of Dijkstra maps, can it do all the things listed in the link too?
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
User avatar
milon
Party member
Posts: 472
Joined: Thu Jan 18, 2018 9:14 pm

Re: Dijkstra Maps implementation rotLove

Post by milon »

Here's a comparison of the two:
http://theory.stanford.edu/~amitp/GameP ... rison.html

And here's an introduction to A*:
https://www.redblobgames.com/pathfindin ... ction.html

They're both written by the same guy. Amit writes some good stuff. :)
My understanding is that Dijkstra is good for maps that don't change and have a fixed goal (or else you can compute one for each individual goal). A* is much more dynamic and flexible, and can be used on-demand (rather than pre-computed), but a little less performant.
Any code samples/ideas by me should be considered Public Domain (no attribution needed) license unless otherwise stated.
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Re: Dijkstra Maps implementation rotLove

Post by Gunroar:Cannon() »

Wait, isn't A* an improvement of Dijkstra and supposed to be faster? And are Dijkstra maps loaded again everytime a creature on a map moves?
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
User avatar
milon
Party member
Posts: 472
Joined: Thu Jan 18, 2018 9:14 pm

Re: Dijkstra Maps implementation rotLove

Post by milon »

They're two different ideas.

Dijkstra maps are pre-calculated to get you from any point on the map to a static goal. They work only when the map doesn't change (as they've already calculated the path(s) for the entire map). If monsters can wander around and block your path, a Dijkstra map would fail (or perhaps collide with said monster). Once calculated, this has the best performance (again, assuming the map isn't dynamic).

A* maps can be pre-calculated, but are usually called as-needed. It doesn't calculate the entire map - only a "best route" from Point A to Point B, based on various input factors. You can tighten them up to be certain they give the best path, or loosen them a bit to come up with a "good enough" path. A* doesn't have the pre-calculation investment of Dijkstra, and it handles changing conditions just fine.

Which one you pick depends on your use case. Honestly, you can use either one as long as 1) you're not running on potato-level hardware and 2) you're not pathfinding for too many entities too often. Either way, I encourage you to read further about both topics.
Any code samples/ideas by me should be considered Public Domain (no attribution needed) license unless otherwise stated.
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Re: Dijkstra Maps implementation rotLove

Post by Gunroar:Cannon() »

Ok, thnx. I did read up on Dijkstra maps and pathfinding a little :)
Do you know how to use the Dijkstra map in the rotlove code?
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
User avatar
milon
Party member
Posts: 472
Joined: Thu Jan 18, 2018 9:14 pm

Re: Dijkstra Maps implementation rotLove

Post by milon »

I do not - I haven't looked at any of the rotLove stuff.

And I can see why we were on different pages regarding A* - I just reread Amit's comparison and he does make it sound like A* is an extension (or hybrid) of Dijkstra. That may be technically true, but it doesn't convey everything Dijkstra is capable of or useful for. You can see another take on Dijkstra here: http://www.roguebasin.com/index.php?tit ... kstra_Maps

Hope that's helpful!
Any code samples/ideas by me should be considered Public Domain (no attribution needed) license unless otherwise stated.
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Re: Dijkstra Maps implementation rotLove

Post by Gunroar:Cannon() »

It was helpful :awesome: , though I already read it and linked it as "brogue here" in first post ^^ . Still good though.
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
User avatar
milon
Party member
Posts: 472
Joined: Thu Jan 18, 2018 9:14 pm

Re: Dijkstra Maps implementation rotLove

Post by milon »

LOL, yep, my bad. :3
Any code samples/ideas by me should be considered Public Domain (no attribution needed) license unless otherwise stated.
Post Reply

Who is online

Users browsing this forum: Google [Bot] and 54 guests