Smart path finding algorithm suggestion needed.

Question

I'm writing a small program for my leisure.
The program will create a 3D dungeon, the size is base on the user input.
It has a starting point and an exit point, filled with any number of treasure.
The idea is to let user enter a direction, visit all the block before exiting the dungeon.

And this is the part I'm struggling, I need a function to check if the dungeon has any valid escape route.
I wrote the has_escape_route() function.
The idea is to check all adjacent grids against the last move.
Since the player can move to 5 different directions in theory (except the starting point, which has 6 possible moves), "path to evaluate" growth exponentially, eventually running forever even the dungeon is shaped 3x4x4. For a small dungeon like 2x3x3, it takes around 10 seconds to finish the calculation on my 12th gen i5 laptop.

This is the code I come up with so far.

Is there any smarter method instead of brute force?

https://sololearn.com/compiler-playground/cF4W4g08p9rl/?ref=app

Answer 1

Pathfinding is a typical problem in programming, so you should be good to go with any of the common algorithms.

Your dungeon is essential a graph. Each block is one node in this graph. Libraries with graph data structures could be an inspiration?

https://medium.com/ironequal/pathfinding-like-a-king-part-1-3013ea2c099

Answer 2

This is a good course to take. https://www.khanacademy.org/computing/computer-science/algorithms
It it also explains route finding.

Answer 3

Q: I need a function to check if the dungeon has any valid escape route.

Ans: You own the program! For everything sake, you either forced a specific dungeons to have an exit route manually and note them down possibly in a json to be used later. This is the most commonly accepted method in game development but If that is not sufficient for you, then i welcome you to the algorithm "Recursive backtracking", but i will explain using iteration. The implementation is very hard, but i will make it simple to understand in c++ (i hate python). You will heavily rely on the LIFO data structure, aka "stack"

struct Grid {
uint x;
uint y;
std::vector<Grid*> neighbors;
int isVisited = 0;
}

BEFORE RUNTIME:
you have to loop through the whole dungeon and create a `Grid` object noting down their x, y, and neighbors(adjacent grid)

While True and Any Grid unchecked:
- loop through the whole grid again, take a current cell,
- check if any of it's neighbor is open
- make the neighbor the current
- push them to the stack

isVisited &= 1

if( you meet a dead end) {
// pop from the stack
// make the popped the current
// go back to while loop
}
}

with this, you will always have the last grid has a "path" (escape route) or a "block" (no escape).

If you need further help on this, share a link to the source code (github or gitlab). Never on sololearn

Answer 4

Hi Lisa! Trust ik you. not quite safe on here.. pls add me on discord @taxevader_camgirl

Wong, Have you heard of the A* Algorithm ? But then you need to specify a destination too. In this case (you don't even know what that is). I will agree with RuntimeTerror. You should use a json and predefine all possible cases.

But i want to assume that this can be done using trees, graph or nodes. You need to be very advanced tho

Answer 5

RuntimeTerror Mel

At the very beginning, I already mentioned I write it for my own leisure.
In fact, I'm trying to mimic a mini-game from "Unchartered Water 3 Costa del Sol" released in 1996 for Win 95 / 98.
Predefining escapable dungeons is not an option because I'm the player.

The game has a very specific requirement: 1. All grid must be visited before escaping; 2. No grid can be visited twice.
This video shows how the game works.
https://youtu.be/WBffqwY6OY8?list=PLbDu9YqydnZqeCmXmu9EN8yDDIVTBlONu&t=454

I didn't read about A* algorithm before Lisa posted the link.
From what I understand from the link, A* algo is mean to find a "mostly direct route" to the exit. In contrast, I need the "most indirect route".

Maybe I need a way to evaluate one route at a time. If the route doesn't match the requirement, go back one step and explore the alternative.

Answer 6

Wong Hei Ming seems there's a confusion.

CASE ONE
___________
1. EVERY dungeon has an escape route
2. All grid must be visited before escaping

CASE TWO:
___________
1. SOME dungeon have escape route
2. All grid must be visited before escaping

Which of these is correct ?

Answer 7

RuntimeTerror

The dungeon is generated randomly, but not predefined, that is why it does not guarantee there is an escape route.
Since I want to make sure the dungeon is escapable, thus created has_escape_route() function.

So that is CASE THREE:
1. The newly generated dungeon has an escape route;
2. All grid must be visited before escaping.

Further into the logic. If the dungeon is not escapable, generate a new one until it is escapable, then start the game.

Answer 8

Wong Hei Ming , it all comes down to the recursive backtracking I mentioned earlier.

There are other several algorithms that guarantee an escape route for dungeons, including

- randomized kruskal
- randomized prim
- Wilson algorithms
- Aldous brouder

But to be fair, recursive backtracking is the easiest. I'll try the implementation in the coming future but here is a sample to recursive backtracking

To make sure all grid have been visited is equally easy to implement now, all you need is to keep track of the grids and set the last grid to "open"
https://sololearn.com/compiler-playground/WFbSDOED7la1/?ref=app