If the queue is empty without the mouse being found, there is no path between cat and mouse. It is irrelevant because the cat has to do only one step, and after that, the shortest path is calculated again (because the mouse is moving too, and the shortest path could lead in a different direction in the next step). The path can no longer be inferred from the data at this point. Termination condition reached - shortest path found Keeping the outer wall in this array simplifies the code, which does not need separate checks for reaching the edges. The maze is stored in a two-dimensional boolean array called lab. The coordinate system starts at the upper left corner of the labyrinth with (0,0). The following images and animations use the labyrinth shown above with the cat at position (15,7) and the mouse at position (11,5). At this point, I use a queue known from the breadth-first search to store the fields to process in the next step. It would be quite slow to search the whole labyrinth at every step. The Lee algorithm has the disadvantage that in the end, you have to go back all the way ("backtrace") to find out which direction the cat has to take.įurthermore, the algorithm does not specify how to find the "neighbors of points marked with i". Without knowledge of this algorithm, I had developed an optimized variant of it, which I will present step by step in the following chapters. In the end, I solved it – as I was to find out years later in my computer science studies – with a variant of the Lee algorithm. But calculating the shortest path between cat and mouse caused me headaches for months. I had quickly implemented the display of the mazes and the control of the mouse. My uncle let me experiment with this computer as a child.Īt that time (I was about ten years old), I was already interested in programming and wanted to reprogram the game on my C64. My favorite example for solving the shortest path problem is the game "FatCat" on the HP-85, a computer from the 1980s. Maze Algorithm: How to Find the Shortest Path in a Labyrinth? ![]() In the remaining part of this article, I explain an optimized version of the Lee algorithm using an example with animations and Java source code. On two-dimensional, tile-based maps, such as those used in early computer games, we can also use a form of breadth-first search known as the Lee algorithm. the A* search algorithm (pronounced "A Star").The best known shortest path algorithms are: That is then generally referred to as pathfinding. Graphs can be very complex and contain millions of nodes and edges (for example, in a video game world where hundreds or thousands of characters can move around freely), so finding the optimal path would be very time-consuming.įor certain applications, it is sufficient to find a reasonably short (or even any) way. ![]() It can also be time (freeways are preferred) or cost (toll roads are avoided), or a combination of multiple factors. The term "short" does not necessarily mean physical distance. 4 Summary and Outlook Shortest Path or Pathfinding?Ī shortest path algorithm solves the problem of finding the shortest path between two points in a graph (e.g., on a road map).
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |