Dijkstra on real map data with raylib

by uysalibov • 2 years ago

89 24 2 years ago

Very much cute :D

And I gotta agree, raylib is cute lil' library. And I love the fact that it has bindings to so many languages, and e.g makes making games in Common Lisp a joy. Or any language, that one would want to use.. well not all, but a lot.

uysalibov5• 2 years ago

Thank you. I really like raylib. It's so powerfull.

richrichie• 2 years ago

Raylib is amazing.

throwaway4259332• 2 years ago

Great work but I cant relate to it because I am not from Istanbul?

How do I add it for other cities. Specifically, for San Francisco Bay area or for Hyderabad, India.

unclad5968• 2 years ago

Looks like the file loading for the map data is hard coded into the initialization.

uysalibov5• 2 years ago

Yes, I do like that. My istanbul data hard coded. But i want to add data import menu. It's on my todo list.

gfiorav2• 2 years ago

The files under Maps/*.json seem to be generated via https://wiki.openstreetmap.org/wiki/Overpass_API

You can generate your own and rebuild

throwaway4259332• 2 years ago

Thx. Any instructions on how to "generate your own" would be appreciated.

pvo505552• 2 years ago

What would be the best way to generate custom maps for use with an algorithm like Dijstra's or A*? I have seen some methods using various game level editors to output to a grid, but is there an easy way to draw custom maps, such as indoors locations, and create your node map with additional JSON data visually?

cornstalks2• 2 years ago

Reminds me of this Reddit post of using A* on a real map: https://old.reddit.com/r/dataisbeautiful/comments/172b8as/oc...

Unfortunately I don't think the Redditor shared their code.

uysalibov5• 2 years ago

Yeah, I saw that video too. But it's created with Python and Blender.

cornstalks2• 2 years ago

I'm curious what your results would be if you switched to A*. The heuristic could be as simple as geographic distance, which would still allow for optimal paths but might reduce the amount of searching you do in the opposite direction of your destination.

keyle• 2 years ago

If you're interested in the A* algorithm to implement yourself, here is a solid base as reference [1]

[1] https://www.redblobgames.com/pathfinding/a-star/introduction...

jbl0ndie• 2 years ago

Nice animation! Reminds me of https://isovists.org/

uysalibov5• 2 years ago

Thanksss

tines• 2 years ago

What heuristic distance function is being used? If it were using Euclidean distance, wouldn’t it be a lot more efficient and not pursue paths that are going in literally the opposite direction as the destination?

uysalibov5• 2 years ago

I use Squared Euclidean distance. Yes, dijkstra algorithm like that way. But if you want to pursue to destination i need to implement A* too.

thom• 2 years ago

Yeah, Dijkstra is more for graph search where maybe you have weights but not actual vectors. But this does give a nice visualisation of how far you can get from a single point in a given time.

gfiorav2• 2 years ago

This is very cool! I compiled it on m2 with no problems.

Istambul is an excellent choice. I enjoyed watching the algorithm take for ever to find a route from the most northern part of the river to the other side :)

leoh• 2 years ago

Bravo! Thank you for sharing -- glad to learn about raylib and the overpass API.

kebsup• 2 years ago

At my university, one of the homework exercises was implementing A* on real map data. Really gave a perspective on the speed of computers, from what I remember, it was megabytes of map data of the UK, but calculating the best path from London to Edinburgh was within tens of milliseconds.

lionkor• 2 years ago

FYI the build steps should be simplified to

    cmake -B build -S .

    cmake --build build

this will work on all platforms.

ms-menardi• 2 years ago

Raylib is the best visual library for C! You can do whatever you'd like, as long as you can program it, which is always the most interesting part of the day.

Dijkstra on real map data with raylib

Related Stories