Game Development Stack Exchange is a question and answer site for professional and independent game developers. It only takes a minute to sign up.
Sign up to join this community
I'm having a school project to create an 2D AI racing car game, but nobody know where is the destination, and the map is randomly generated. But to avoid the dead end, we must teach the car not to move to that path again. I wonder if there were any algorithms or methods to store the dead end which was passed. I have searched the A* algorithm but I think that algorithm doesn't help me in this case.
The map should look like this:
And this is the road:
Do you generate the whole map at once or do you only generate in increments?
If you generate the whole map at once, then you generate the goal and thus you could use A* or similar algorithm without any modifications.
If you just do not know where the goal is, A* still works. A* will exhaust all paths until it finds the goal or fails. However, you may lack a good heuristic because you do not know where the goal is, so you could tweak A* to work without it (or use Dijkstra's algorithm).
On the other hand, if you generate in increments, the goal might not be in the map yet. This means that you need two different behaviors:
To "store were any algorithms or methods to store the dead end which was passed" you use influence maps. It is a structure that mimics (or is attached to) the actual map where you store what have been visited. You could have an influence map per agent, or multiple agents can share a single influence map, that depends on what you want.
Now, exploring is easy: pick a known open path or unexplored area (usually something at the edge of what you have explored), set it as target and go there. This should reveal/generate more parts of the world. You continue to do this until you run out of areas to explore or you find the goal. Which place do you pick to explore? You probably want to pick the closest to the agent, however picking at random should still work. I would like to encourage experimentation.
And of course, once you have discovered your goal you can try going there... there is a chance that you found the goal, but not the path to it. No problem, A* will find a way... you just need to know the following: each frame/turn you just need to decide on what direction to move, not the whole path. So, if you set a maximum number of iterations for A* per frame/turn, or let it run until you exhaust some percentage of your time budget for the current frame, you can pick the best of the paths it found (you have an admissible heuristic, right?) and follow that one.
I'll plug here my answer to Java Game Loop Efficiency, you could find it useful.
What I said above should be enough to solve the problem. If you are looking for something different keep reading.
If all else forms of searching fails, there is good old breadth-first search, which should explore without any information of the goal. You might also be interested in D* Lite.
If you want a more general solution, you might look into Q-Learning or SARSA. You could feed an admissible heuristic as reward for it. It does not require knowledge of the world (so no influence map, and no location of the goal), instead it uses table that relate actions and probable outcomes.
See the lecture MIT 6.S094: Deep Reinforcement Learning for Motion Planning video (1 hour 27 minutes 29 seconds) for a detailed explanation of Q-Learning.
Given the nature of the mazes, a randomized recursive back-tracker is a good solution. Why? Because that is likely how the maze were created in the first place. A maze generation algorithm based on this fills the map, has no large rooms - only corridors and intersection - has no disconnected areas, has no loop, lots of dead ends and no large scale structure.
How to solve a maze with a randomized recursive back-tracker?
At every moment you look at the paths you could take (excluding those where you have already been) and if there is only one path, you go that way, if there are many you pick at random, if there is none, you backtrack (meaning you go back from where you came).
To know your path, you store a stack of the positions you have been, so you can push to the stack every step you make, and pop when you backtrack. However you do not want to go down the same path you went last time (you know it is a dead end), so you need to also keep a list of visited positions (or given that the map is on a grid, you can have an array of bool where you set true to mean visited).
This algorithm is guaranteed to visit the whole map. However, it is unaware of the goal. If we know where the goal is - and since it is randomized - we can tweak it with a heuristic based on the location of the goal. Instead of going at random, we pick the direction that moves closer to the goal.
Similarly you can use this algorithm to create a maze. At the start you could go in any direction, however, since you will not step where you visited, you will eventually get to a dead end (trapped by your previous path) at which point you backtrack, and then branch at some earlier point, and keep doing this until the whole available are has been carved to a maze (you know you finished because you should backtrack but there is no more to backtrack, you are where you started).
If you do not know the location of the goal, but you know the size of the maze and that the goal is likely away from the start, you can create a heuristic based on how far you have moved from your starting position. Remember that heuristic in path finding use an estimations of the distance to the goal... so you could take the diameter of the maze and subtract how far from the start you are. However be aware that this would not be considered an admissible heuristic because it can over estimate the distance (if your teacher sets the goal close to the start, it becomes a bad heuristic). If your algorithm is guaranteed to explore the whole map, using a not admissible heuristic will not prevent getting to the goal, but it will be very inefficient.
Also, remember that your map knowledge representation (influence map et.al.) does not have to match the world one to one. Working with a coarser representation can make the code run faster even if that means it is less precise. I do not know with how much resolution you can steer the car, however, as far as path finding is concerned the road could be made of line segments or a very large grid compared to the car. In fact, in some cases, we use multiple representations at different levels of resolution.
