The Caver Algorithm
Loading...
Link to this comment:
Uploader Comments (RJLeffmann)
Video Responses
All Comments (29)
-
When I did a maze generator a long time ago, I had a parameter telling the chanse of continuing to dig straight forward or to turn left or right. That way I could set how wriggly the maze would be.
Another parameter I would introduce if I did this today is a random chanse to stop digging and start a new branch. This way I could set if there will be few or many dead ends.
-
This is very similar to Trémaux's algorithm.
-
what's the maze generation algorithm?
-
I did this in college.
You can improve the maze-generating algorithm by starting at the end and generating towards the start. This means the start square will likely have two paths, one of which will always be a dead end. If you generating starting at the start, the end square will have two paths, one of which will never be traversed.
(continued)
1:52
... And that's One Million particles!! #3: I should make this into a demo...by lievenvv114,090 views- 0:30
A* (AStar) Pathfinding algorithmby Wigpo6,608 views
- 4:53
The Algorithm - Geometric Progression [2009]by TahitiBob40,667 views
- 2:11
NXT Maze Solver that Remembers the Shortest Pathby javierantonioruiz21,694 views
- 1:07
A* Pathfinding Algorithm Visualizationby TheBartR2,989 views
- 0:27
Animation of a binary tree in Javaby 2k1ppp13,383 views
- 2:24
SimplePath - 500 Agents Pathfinding + Dynamic Obstacle Avoidanceby alexkring7,713 views
- 0:32
Escalator - Safe Use (Chinese Version)by EMSD30039,774 views
- 2:14
Genetic Algorithms: Evolving a human faceby ldbrandy29,609 views
- 0:38
EPIC Escalator Trick FAIL!!by antoniorios961,080,117 views
- 0:53
Vídeo sobre Heap Sortby Marmelcartiger18,667 views
- 2:05
My FPS made with c++by LearnGameProgramming20,821 views
- 1:40
RTS A* Pathfinding with squadsby y4ure2,625 views
- 1:19
Genetic Algorithms: Mario level 1-1 Completely Random Jumping.by evolsoulx24,454 views
- 0:25
Map Creator for a Tactics RPG Gameby zoser26,457 views
- 1:18
Windows 98 3D Maze LEVEL 3by GX3876,728 views
- 0:42
XNA Maze Generatorby exceptionthrown9,294 views
- 9:39
dijkstra 1by udimamoreno24,688 views
- 1:21
Suicidal Slinkyby funkyfunkyjoe26,140 views
0:26 and 0:36, assuming the solver knew the boundaries of the maze, it should have also known that the directions it headed were dead ends. Euclidean distance checks at T intersections are the key here :)
trjnz 3 months ago
@trjnz Yes - given that it's trying to reach a known coordinate. If you're trapped in a maze then you probably don't know where the actual exit is :)
RJLeffmann 2 months ago
Is this an example of backtracking?
metabog 4 months ago
@metabog Yes it is. Both the generator and solver are depth-first search algorithms that will track back when they find themselves in a dead end that will not lead to a solution.
RJLeffmann 4 months ago 4
You can also improve the maze solving algorithm by making it try squares that reduce the euclidean distance to the end in most-to-least order, since solutions are more often direct than not.
domokato 1 year ago 2
@domokato Good thinking, and I agree on the heuristic for solving the maze, it would probably make it a lot quicker. I'll try it out some day.
RJLeffmann 1 year ago 2