Path Finding Algorithm with GUI

In computer science class at my university, our professor showed us an algorithm for finding a shortest path between two points on a grid with obstacles. Here is an implementation I made in C with a GUI.

It uses the SDL library for keyboard/mouse input and OpenGL for drawing.

The algorithm behind it is pretty fast; it finds solutions in less than a second, even on a 1000x1000 grid.

It supports reading from/writing to files in an ASCII-based format.

Category:

Film & Animation

Tags:

• shortest
• path
• finding
• algorithm
• gui
• sdl
• opengl
• programming

[Benedek93]

@Kinderlabor Thanks :)

[Kinderlabor]

@Benedek93 The algorithm is called "breadth-first search".

[Benedek93]

@Danny77uk No, I'm not sure if this algorithm has a name, our professor showed it to us. Actually, now that I looked into it, it's sort of like the "Sample algorithm" shown on the Wikipedia page on Pathfinding (look it up, apparently I cannot post links here).

[Danny77uk]

A*?

[Benedek93]

@rinsmaster Yeah, it does only look in 4 directions, but it should always find one of the shortest paths available :-)

[rinsmaster]

Awesome! It's not the shortest path is it though? Well in Manhattan-distance it is I guess :) (compared to A* which creates semi diagonal lines)

But this is quite relevant to me, I was actually doing some research on path finding for my entry to Google's AI Challenge.