Let the stars align

It’s time to code the spine of this whole operation, implementing A* to find the shortest path.  I thought this would be challenging which is why I guess I put it off for so long but it’s actually lots of fun trying to optimize it.

Anyways after some testing, I’m not sure A* is the best solution,  it ends up solving a lot of the maze anyway and the closed list grows in excess ot 50000 elements.  I’ve come up with another idea where I might either take A* with no heuristics which is pretty much Dijkstras (spelt it correct on the first try, wsup) and only keep track of elements on the edge as there is no point in scanning an item in the closed list that is impossible to hit.

While trying to implement it I did however come across many cool data types like heaps, trees and even had to pull out the good Ol’ big O notation from MACM to choose the best sorting algorithm which I think is this case is insertion sort since the data will always be presented in a best case scenario and gives O(n). Binary heaps might also do the job better so it’s time to play around and see.


Tags: ,

About jjyap

I'm an undergraduate student at Simon Fraser University. A lot of the fun projects and research that I work on are Computer Vision and Machine Learning related.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: