Results 1 to 9 of 9

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

  1. #1

    Thread Starter
    College Grad!!! Jacob Roman's Avatar
    Join Date
    Aug 2004
    Location
    Miami Beach, FL
    Posts
    5,333

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

    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.
    Attached Images Attached Images  
    Attached Files Attached Files

  2. #2

    Thread Starter
    College Grad!!! Jacob Roman's Avatar
    Join Date
    Aug 2004
    Location
    Miami Beach, FL
    Posts
    5,333

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

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

  3. #3

    Thread Starter
    College Grad!!! Jacob Roman's Avatar
    Join Date
    Aug 2004
    Location
    Miami Beach, FL
    Posts
    5,333

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

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

  4. #4
    Fanatic Member BlindSniper's Avatar
    Join Date
    Jan 2011
    Location
    South Africa
    Posts
    865

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

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

    Useful CodeBank Entries of mine
    Expand Function
    Code Compiler
    Sudoku Solver
    HotKeyHandler Class

    Read this to get Effective help on VBForums
    Hitchhiker's Guide to Getting Help at VBF

  5. #5

    Thread Starter
    College Grad!!! Jacob Roman's Avatar
    Join Date
    Aug 2004
    Location
    Miami Beach, FL
    Posts
    5,333

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

    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.

    Code:
            '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;

  6. #6
    Fanatic Member BlindSniper's Avatar
    Join Date
    Jan 2011
    Location
    South Africa
    Posts
    865

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

    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.

    Useful CodeBank Entries of mine
    Expand Function
    Code Compiler
    Sudoku Solver
    HotKeyHandler Class

    Read this to get Effective help on VBForums
    Hitchhiker's Guide to Getting Help at VBF

  7. #7

    Thread Starter
    College Grad!!! Jacob Roman's Avatar
    Join Date
    Aug 2004
    Location
    Miami Beach, FL
    Posts
    5,333

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

    More updates located above. Fixed some minor issues.

  8. #8

    Thread Starter
    College Grad!!! Jacob Roman's Avatar
    Join Date
    Aug 2004
    Location
    Miami Beach, FL
    Posts
    5,333

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

    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.

  9. #9

    Thread Starter
    College Grad!!! Jacob Roman's Avatar
    Join Date
    Aug 2004
    Location
    Miami Beach, FL
    Posts
    5,333

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

    (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.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width