(VB6 & VB.Net) A* Pathfinding (Fast and Easy)

[Jacob Roman]

You won't find code like this anywhere. I have here a very fast and easy to understand A* Pathfinding algorithm (pronounced A Star) that can easily be ported to any game you are making. It finds the fastest route from the starting point which is your predator to the ending point which is your prey. I have ran into other A* programs in VB and found them to be very ugly. Ran into one I found too dependent on values I did not wanna use and found it wasn't the proper A* structure (not to mention it was nearly impossible to port into my game), and another that was easy to understand, but locks up in certain areas on the map and was hideously slow. Sadly I used that slow and easy method on my Bosskillers game which will be corrected. I organized my code to easily break it down and have it commented. For more documentation on A* Pathdfinding, refer to this website:

A* Pathfinding for Beginners

[EDIT] Massive improvements have been made and this is probably the ONLY A* Pathfinding program that actually includes the monster following the path! And you can move your player through the map. It even has collision for the walls. For optimization purposes, the A* Pathfinding only needs to be computed when the monster moves to a new map coordinate.

[EDIT] Another Improvement has been made. I noticed 2 things. One, that the path disappears once in awhile for a split second even though the predator continues to follow the path. Turns out the player needed a role as well in enabling Compute_AStar_Pathfinding. So whenever the player moves to a new map coordinate, it fires AStar. The other problem was that very very rarely it locked up. Having the player play a roll in Compute_Astar_Pathfinding fixed this as well. No more lock ups. Lockups tend to be the biggest problem with AStar samples and can cause your program to hang. I also changed the order it was in the Game_Loop. So it is now this order:

• Keyboard Controls
• Clear Screen
• Collision
• AStar Pathfinding
• Follow AStar Path
• Render Map
• Draw AStar Path
• Draw Monster
• Draw Player
• Lock_Framerate 60
• DoEvents

Also another improvement I made is that if the monster trys to leave the map screen, itll stop at the edge. However you can leave the map screen with no problem. Itll stop computing AStar when the player is out of the map boundry and the monster continues following the path it has created for itself. AStar samples I tested had Subscript out of range errors for doing so! So my AStar seems to be the best out there so far on the web. I may port this to VB.Net as well and make other improvements such as how the monster interpolates from one tile to the other. Currently although it works, it has issues when the next path for it to follow is at an angle and theres a wall there so it drags along the wall till it goes to that tile.


[EDIT] Another big update that took me months to solve. There is no longer any jittery movement with the sprite when the A* path changes. The reason this jittery movement happened was because the sprite wasnt done moving to the next node, and when there was a change in path, the sprite tries to move to the first node of the path, hence the jittery movement. So I made it to where the monster must complete the path to the old node before it can start following the path of the new node. As a result the movement is as smooth as silk. Also I cleaned up some of the code, removed a couple useless objects, improved the path change when moving the player or sprite, and removing the walls is very smooth now cause you can now just hold the mouse down and move the mouse to remove the walls easily.

[ANOTHER EDIT] Added a VB.Net version of the same exact program.

[Jacob Roman]

Heres a VB.Net version which is similar but not my code.

[Jacob Roman]

Huge huge update has been made to this program on VB6. The updated one is located above with description of update

[BlindSniper]

Does A* Always find the best path or only an optimal path ?

[Jacob Roman]

A* finds the fastest and shortest route for the predator to reach its prey. So yeah the best path. There are other algorithms you can use for the Heuristic as well, but Manhattan is the fastest and most basic.

        'Case HeuristicType.Manhattan:
        '    H = Math.Abs(StartX - EndX) + Math.Abs(StartY - EndY);
        '    break;

        'Case HeuristicType.Diagonal:
        '    H = Math.Max(Math.Abs(StartX - EndX), Math.Abs(StartY - EndY));
        '    break;

        'Case HeuristicType.Euclidean:
        '    H = Math.Sqrt(Math.Pow(StartX - EndX, 2) + Math.Pow(StartY - EndY, 2));
        '    break;

        'Case HeuristicType.EuclideanSquared:
        '    H = Math.Pow(StartX - EndX, 2) + Math.Pow(StartY - EndY, 2);
        '    break;

        'Case HeuristicType.TieBreakerManhattan:
        '    H = Math.Abs(StartX - EndX) + Math.Abs(StartY - EndY) * m_tieBreaker;
        '    break;

        'Case HeuristicType.TieBreakerDiagonal:
        '    H = Math.Max(Math.Abs(StartX - EndX), Math.Abs(StartY - EndY)) * m_tieBreaker;
        '    break;

        'Case HeuristicType.TieBreakerEuclidean:
        '    H = Math.Sqrt(Math.Pow(StartX - EndX, 2) + Math.Pow(StartY - EndY, 2)) * m_tieBreaker;
        '    break;

        'Case HeuristicType.TieBreakerEuclideanSquared:
        '    H = Math.Pow(StartX - EndX, 2) + Math.Pow(StartY - EndY, 2) * m_tieBreaker;
        '    break;

[BlindSniper]

Ok, thanks for clearing that up, I was mixing algorithmic pathfinding up with genetic programming pathfinding. The latter only gets an acceptable path and not always the best.

[Jacob Roman]

More updates located above. Fixed some minor issues.

[Jacob Roman]

It took me months to solve but I fixed the above program big time. On top of the updates I mentioned in the first post on the bottom, most importantly eliminating the jittery movement of the sprite, I also improved how the sprite moves node to node. A total change has been done to the AStar following code. It constantly moves the speed given. The interpolation has been removed because it wont take certain values, mostly being the decimal values, and its not as consistant as my new code. Now you can have the sprite move at literally any speed chosen. Enjoy the new program, and I strongly recommend this to anyone designing a game where chasing is involved. Also I strongly recommend you update the old A* code with this new one due to the majority of the issues I have had.

[Jacob Roman]

(Update) I added a VB.Net version of the same exact code as my VB6 version, only I'm using DirectX instead of generic graphics. You can find it in the first post.