Search algorithms

[danger] The version on Reeborg's World may not be compatible with the code presented here.

This will be fixed in the near future.

Many problems can be solved by using an appropriate search algorithm. These algorithms are relatively advanced programming topics and are definitely not suitable for beginning students. We discuss them in this chapter to illustrate how Reeborg's World can be used to teach advanced topics. I will use an introduction to the A* algorithm as the basis of the presentation; by the end, you should have all the information you need to use Reeborg's World as a demonstration platform for other search algorithms.

The content of this chapter will follow fairly closely the description and notation used on Amit Patel's Introduction to A*. I have found that Patel's Red Blob Games site to be one of the clearest sites when it comes to describing various algorithms used in games. His combination of clearly written code and interactive diagrams is truly outstanding. He has also helped with creating more interactive examples used to illustrate Artificial Intelligence: a Modern Approach, by Russell and Norvig. You can also have a more detailed look at the code he uses for his implementation of the A* algorithm.

It is my hope that by using Reeborg's World to run some code examples provided in this chapter, and modifying them at will, can provide a complementary approach to those mentioned above and contribute to a greater understanding by the students.

[success] Useful resources

If you need to copy-paste some examples from this chapter, it may be easier to do it using the raw version of the source files as it would ensure that the indentation is preserved.

Also, you may want to do:

import search_tools
help(search_tools)