Swizzbeat's Modified A* Pathfinder

February 4, 201412 yr

Hey guys, just thought I'd release this to get some feedback on what I've been doing. Basically all I did was read a few articles on the A* pathfinding algorithm and attempted to put what I read about it into code. This means it most likely is not anything how A* should actually be written (I've personally never even seen A* code and my version doesn't even use two lists) so that's why I'm saying it's my own modified version. A picture of the application I wrote to graphically represent the code can be viewed below:

The code is very messy and multiple spots are hardcoded so the algorithm will only work with this program, but I'm working on fixing it up. Also, I know it doesn't find the "best path" as evidenced by the above picture because of the overflow effect produced when it hits a U-shaped path blocker. This isn't a main concern of mine right now because I will be using this to write an OSBot web walker, which won't include any blockages due to all the nodes being predefined, but in the future I hope to fix this issue and incorporate a best path in.

If you're interested in running the application yourself the jar file can be found HERE. To use just hold down your mouse button/click to create an obstacle tile, and press enter to find the path (blue represents tiles searched and cyan is the actual path). Any and all feedback is welcome

Edited February 5, 201412 yr by Swizzbeat

1

February 4, 201412 yr

Super interesting, nice one swizzy

February 4, 201412 yr

Nice looking application c:

although it can be improved in a few places :E, I see you're manually searching for the best node for each iteration; Which is extremely costly compared to using a PQ which does this for you upon insertion

February 4, 201412 yr

Author

Nice looking application c:

although it can be improved in a few places :E, I see you're manually searching for the best node for each iteration; Which is extremely costly compared to using a PQ which does this for you upon insertion

What exactly is PQ? I'm very new to this pathfinding stuff, and like I said I've really never even looked at pathfinding code

February 4, 201412 yr

What exactly is PQ? I'm very new to this pathfinding stuff, and like I said I've really never even looked at pathfinding code

a PQ isn't exactly pathfinding specific

a PQ is this

1

February 4, 201412 yr

What exactly is PQ? I'm very new to this pathfinding stuff, and like I said I've really never even looked at pathfinding code

PriorityQueue sorts whatever you insert into it by using its compareTo method; So you will want your NodeRectangle class to implement the Comparable interface (Comparable<NodeRectangle>), and compare their F values; Then calling poll on the PQ will always retrieve the best node with O(1) efficiency, and inserting into the PQ is O(log2n) efficiency