Point ROBOTs’ shortest path in point obstacle field mapped by Dijkstra’s algorithm:
1. Build Voronoi diagram of the obstacles
2. Transform Voronoi diagram into a graph
3. Make sure edges are weighted by distance
4. Find shortest path on the graph using Dijkstra
This is really cool! What if you added another color to highlight the path with the shortest distance? So as the target moves it highlights which robot has the shortest path
Great work
You’ve made slime mold lol this is close to how it feeds and moves!
When I accidentally allow my map app to update on the fly.
The obstacles you generatred from the voronoi graph seem like something one could do in a video game to add “flavor” to an enemy’s pathfinding.
So if you didnt want an enemy that follows a player to always move in a straight line, then they could follow this variance by instead navigating the path made by the obstacles.
To be clear, Im imagining this as “invisible” obstacles, used purely to make a unique, random, set of paths for enemies to follow. You could also apply true obstacles over top the generated obstacle path to have varying paths + build in avoidance of genuine walls, etc.
Very cool and thought provoking visual, thanks so much for sharing!
This looks absolutely insane on my phones oled display
I only knew about Dijkstra in OSPF in networking. I had no idea it could be used in this kind of setting. Where else do we use it?
Is Dijkstra the one that came up with the logic we use in GPS systems?
I have absolutely no idea what I am looking at.
It is not very clear what is meant by “shortest path”: specifically the shortest path along the edges of the Voronoi diagram?
I think you mean shortest paths while avoiding obstacles at all costs. (Only navigating a Voronoi diagram)
11 comments
CODE, article and higher resolution full video (at the end): [https://community.wolfram.com/groups/-/m/t/3343868](https://community.wolfram.com/groups/-/m/t/3343868)
DATA: simulated, set of random points in 2D plane
TOOLS: Wolfram Language
Point ROBOTs’ shortest path in point obstacle field mapped by Dijkstra’s algorithm:
1. Build Voronoi diagram of the obstacles
2. Transform Voronoi diagram into a graph
3. Make sure edges are weighted by distance
4. Find shortest path on the graph using Dijkstra
This is really cool! What if you added another color to highlight the path with the shortest distance? So as the target moves it highlights which robot has the shortest path
Great work
You’ve made slime mold lol this is close to how it feeds and moves!
When I accidentally allow my map app to update on the fly.
The obstacles you generatred from the voronoi graph seem like something one could do in a video game to add “flavor” to an enemy’s pathfinding.
So if you didnt want an enemy that follows a player to always move in a straight line, then they could follow this variance by instead navigating the path made by the obstacles.
To be clear, Im imagining this as “invisible” obstacles, used purely to make a unique, random, set of paths for enemies to follow. You could also apply true obstacles over top the generated obstacle path to have varying paths + build in avoidance of genuine walls, etc.
Very cool and thought provoking visual, thanks so much for sharing!
This looks absolutely insane on my phones oled display
I only knew about Dijkstra in OSPF in networking. I had no idea it could be used in this kind of setting. Where else do we use it?
Is Dijkstra the one that came up with the logic we use in GPS systems?
I have absolutely no idea what I am looking at.
It is not very clear what is meant by “shortest path”: specifically the shortest path along the edges of the Voronoi diagram?
I think you mean shortest paths while avoiding obstacles at all costs. (Only navigating a Voronoi diagram)
Comments are closed.