Projek Baru ...

Ok ... the game is going fine and all, however I have been persuaded to join my friend, Marwan in exploring this Algorithm called A star. To be honest, it's exactly the same as Dijkstra. The only difference is dijkstra uses a queue. A star uses a Priority Queue based on the cost, therefore reducing the total number of nodes that have to be explored. Hence, improved performance. The path obtained depends on the heuristics, sometimes the result will be optimal, sometimes not.

In all algorithms that find a shortest path, it simplifies a complex data structure and turns it into the simplest, a list. The goal is creating the shortest list possible by eliminating all the possible nodes that could be used to get to the destination.

This A star algorithm calculates cost using heuristics, unlike Dijkstra which uses actual path values. It is actually a combination of both Best First and Dijkstra. It will behave like Best First until it reaches an obstacle. Then it will show behavior similar to Dijkstra path finding. In other words it will start to explore. The red path shows the shortest path. The faint red/pink pixels are those that are explored once the 'explorer' hit head first into the dark grey obstacle.

To get this optimum path I came up with this Heuristic function:

H(n) = distanceFromStart + accumulatedCost + selfCost + distanceToDestination

Each has its 'weights' to adjust its effect on the output. I set them all to 1. The larger the value of the 'weight', the larger it's effect on the heuristic function calculation.
These are 2 identical maps. As you can see, changing the 'weights effect how many nodes are explored. In this example there is not much difference in path selection.
The diagram on the left uses the following weight values, the one on the right uses all 1's.

distanceFromStartWeight = 0.21
accumulatedCostWeight = 0.5
selfCostWeight = 0.5
distanceToDestWeight = 1


The python program I wrote is about 200 lines long written in maybe 12 hours. It's still pretty basic. I'll include features later on. I actually plan to do map navigating using this algorithm. Still thinking it through. I'll post the code up after I test it and maybe add further features.