CODEWITHSUNDEEP
javapath-findinga-star
Malii
Malii

Reputation: 448

Questions about A* Pathfinding

Well, I'm trying to implement A* Pathfinding into a simple tilemap array and I have a few questions.

For the open/closed list should I just use an arrayList to store all of the points it finds or is there a better method for storing them?

Second how do I go about checking neighbours? Do I take the start tile, check the one above,below,left and right and whichever has the lowest cost is stored?

Upvotes: 0

Views: 306

Answers (3)

Gene
Gene

Reputation: 46960

I have implemented this in the past with a PriorityQueue for the open list. The comparator works on the A* heuristic value. This is very clean and you'll get O(log n) performance per insertion and poll worst case. Better than standard implementations can improve poll to O(1) amortized. For the visited list, use flags in the tiles or else a separate HashSet. The latter has the advantage of no initialization cost and the same asymptotic cost for insert and membership. But the constant factors are larger for a hash than for checking boolean map values.

Upvotes: 1

MvG
MvG

Reputation: 60858

I don't know what a “tilemap array” is, but I assume that by “points it finds” you mean nodes in the search tree. The data structure where you store the node you haven't explored yet needs to fulfil two important properties, inherited from Dijkstra's Algorithm:

  1. Fetching the node with lowest cost should be fast, at least O(n)
  2. You'll want to lower the cost of a node once you find a shorter path

The former can be achieved using a heap. Binary heaps are fairly easy to implement. Fibonacci heaps give beter asymptotic performance, but in most applications shouldn't be neccessary. Most heaps from libraries I have seen so far don't support the latter requirement, often called decrease key. To implement that, your nodes should hold information about their current position in the heap. That way, when a node changes its cost, you can obtain its current position in O(1) and adjust the position in O(log n). And you can use that same variable to decide whether an item is in the heap or not.

Now for your second question. Usually you check costs by removing the minimal element from the heap. In other words, for each neightbour, you either insert it into the heap, or if it already was in the heap, you adjust its cost (and with that its heap position) if the new cost is better.

Upvotes: 0

Raskolnikov
Raskolnikov

Reputation: 296

As long as you aren't implementing this for a game, meaning high-fps video game, I doubt your performance will take a significant hit for using as ArrayList, that should be fine.

As to the second part of your question assuming you only have 4 directions of connectivity for each node then yes, a simple sequential check of each neighbor will work.

Upvotes: 1

Related Questions