AI Fun

Joe's blog about AI things!

Tag: finding

The Master Of The UNIVERSE!

Or, at least, OpenCV. That’s right my faithful readers, I have managed to install it. It took me many days of pain and suffering, but It finally works with Microsoft Visual C++ 2010.

In other, less exciting news, I have been half heartedly working on a function to find the local maxima of an image. This would be easy (look for a change in gradient in both the x and y direction), but the image is full of disgusting noise, leading me to search for a more creative solution. Perhaps some pre-processing is needed? Or maybe some kind of… find a maximum and then ignor any nearby maxima. Could try filling in every change of gradient point, and then convolving with Gauss, and then repeating. Who knows!

A* algorithm in c++!

This is not an algorithm to get you an A* in your GCSE’s. Don’t be so silly. A* (Astar) is a path finding algorithm used to find…. paths.
It is very similar to Dijkstra’s algorithm, if you know what that is. I found a great explanation here: http://www.policyalmanac.org/games/aStarTutorial.htm , so I’m not just going to recreate that in a lesser form without diagrams. If you want to understand it, go check that out.

The following source code  makes no attempt at clarity or efficiency. Nor does it claim to make good use of spelling. It does, however, work. It also has no formatting thanks to wordpress. But perhaps if you cut and paste it into a c++ program, it might get sorted for you. Who knows.

It first randomly generates a small world, which is filled with walls (0’s) and empty space ( ). This is seeded the same everytime, but could be changed with a call to time(0) (#include<time.h> I *think*). The A* algorithm is the called to find a route from the top left to the bottom right.

Next, the end of the A* is printed. Start in the bottom right, and just go in the direction indicated (u for up, r for right, l for left, d for down). Keep doing this until you reach the starting position. Or not if it has failed, which is possible!

Lastly I get the computer to compute the route, and print it out with little @ symbols. Lovely.

SOURCE CODE:

Astar– This is a word document!

Read the rest of this entry »