Exploring Path-Finding Algorithms for Wall-E

Inspiration

As I delved into the topic of well-known path-finding algorithms, I discovered that despite route finding being a solved problem, it continued to be of interest to the professional game development community. Between 2010 and 2020, engineers made significant optimizations to the A* algorithm, particularly beneficial for AAA games with massive maps. Reading articles and research papers on these optimizations was an exciting experience.

I found it intriguing to explore this field and develop a small application that uses well-known graph algorithms to find routes on a grid map. To visualize my findings, I employed the SFML graphics library.

What it does

Imagined a technically advanced and innovative city where the future has arrived long ago. In this city, courier robots deliver most orders, and it has become a rarity for someone to deliver an order from a cafe. In this task, we invite you to participate in finding optimal routes to deliver orders efficiently.

How I built it

Represented a map as a grid of cell. Developed a text representation data format allowing me to design the maps and load it during run time from the source files. Implemented an 2D graphics visualization of the maps and routes using SFML graphics library and C++. Implemented a set of algorithms of finding optimal route on maps.

Accomplishments that I'm proud of

As a result of my experiments, I have published an article about my "Wall-E project" which is a visually appealing implementation of path finding algorithms using SFML graphics library and Yandex data sets. Article has been Featured on Dzone Data Engineering page and reposted on Better Programming Medium Hub, as well as codeproject, hash-node, dev.to (more info and links on my web-site).

Built With

• algorithms
• astar
• bfs
• c++
• dfs
• dijkstra
• graphs
• path-finding
• sfml