[solved] Moving player tile-to-tile (A* Pathfinding finally done)

[TehJavaDev]

@BurntPizza

I think that’s why we are confused, as your thread title is misleading.

Thus me wanting to make a new thread due to a new topic :o
Thanks, I’ll take a look at the link you posted :point:

[TehJavaDev]

@BurntPizza

The A* gives you that path, if you don’t have a path then what you’ve done isn’t A* or any pathfinding algorithm. Maybe you’ve made flood-fill, the first part of such an algorithm?

I followed the instructions on this A* Pathfinding guide for beginners. than created the process in Java (While debugging / fixing for hours to get the same result as instructed) and I came out with the same results as the guide for each step. (Which produce a list containing all the tiles that have been deemed walkable on this path)

I’m just stuck on the final step, “Obtaining the shortest path”.

Summary of the A* Method
Okay, now that you have gone through the explanation, let’s lay out the step-by-step method all in one place:

1) Add the starting square (or node) to the open list.

2) Repeat the following:

a) Look for the lowest F cost square on the open list. We refer to this as the current square.

b) Switch it to the closed list.

c) For each of the 8 squares adjacent to this current square …

If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.           

If it isn’t on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square. 

If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.

d) Stop when you:

Add the target square to the closed list, in which case the path has been found (see note below), or
Fail to find the target square, and the open list is empty. In this case, there is no path.   

3) Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path.

My setup honestly performs ideal for me minus the checking of a gang of tiles when the destinations right around a corner 3 tiles away XD (Flood fill, posted in picture?)

Thanks for helping
All I need to do is create a method that tracks a nodes children until the starting node is found.
(If that makes sense)

[BurntPizza]

Like I said, the 5th section of Amit’s guide:

// The code to reconstruct paths is simple:

current = goal
path = [current]
while current != start:
   current = came_from[current]
   path.append(current)

[TehJavaDev]

The expanding frontier can be viewed as contour lines that stop at walls; this process is sometimes called “flood fill”:

Here though we want to use it for finding paths, so let’s modify the loop to keep track of where we came from for every location that’s visited, and rename visited to came_from:

It seems I’ll be able to fix the floodfill issue ^^ Hopefully ;D
Translating python to java and adaptable for my project should be fun ^^

[TehJavaDev]

I think I’ll take a break from pathfinding in my current game, make a new project and make it a pathfinding system that’s easily implementable and adaptable.

Simple window no other spiffs in the way, window for rendering.

I want to actually get A* correct this time :3

Thanks for your help everyone

[BurntPizza]

Note that just flood fill + back trace is just breadth first search, A* is Dijkstra’s + greedy best first search. They’ll both yield fastest paths, but A* can handle weights and is faster to execute.
Just so you’re aware of the difference.

[rwatson462]

The way I managed to do this in my attempts was like this:

I set up a class that holds 3 values = x, y, next. When I loop over the “frontier” I get each location’s adjoining tiles and store the location in the next attribute.

Something like this:

location = queue.get(0);
newLocations = getAdjoiningTilesTo(location);
//  loop over newLocations and do
newLocations.get(0..size-1).next = location;

When you find your target you can loop over it like this:

location = targetTileFoundByPathfinding;

path = new ArrayList<LocationClass>();
while (location.next instanceof LocationClass) {

  path.add(location);
  location = location.next;

}

be aware though that you end up with the path in reverse
(I know this isn’t great, but it works for me and optimise mine over time)

Hope this helps you!

[Riven]

[quote=“BurntPizza,post:26,topic:50874”]
Dijkstra handles weights just fine :point:

Oh, and A* is not guaranteed to yield the fastest path, as it is heavily biased to a path that lies on the line src→dst, it might not even visit the ‘instant portal’ only a few cells away (in the opposite direction). Dijkstra would handle this odd case just fine, at the cost of worse performance in the general case.

[BurntPizza]

I was saying breadth first doesn’t do weights, could of said that more clearly.

[Jono]

@Riven

Oh, and A* is not guaranteed to yield the fastest path, as it is heavily biased to a path that lies on the line src→dst, it might not even visit the ‘instant portal’ only a few cells away (in the opposite direction). Dijkstra would handle this odd case just fine, at the cost of worse performance in the general case.

If there are portals then instead of just using Euclidean distance from A to B for the heuristic, use (Euclidean distance from A to nearest portal) + (Euclidean distance from B to nearest portal) if that is shorter. Then A* won’t be incorrectly biased and will still guarantee the shortest path.

[Riven]

The portal example was an edge case. There can be an arbitrary number of shortcuts (areas with reduced weight) that A* simply doesn’t touch when it uses a non-zero H.

[Jono]

Fair enough. I suppose the point I really wanted to make was “use an appropriate heuristic and A* will work”.

If there are large zero-cost regions then it is tricky to define something more informative than h=0, but even at that limit A* just becomes Djikstra’s.

[Riven]

(Near)zero-cost is not required, the effect is already observable if we have a parallel dirt road and paved road. Let’s say the edges of the dirt road have cost 1.1 and the paved road has cost 0.9, all other edges (grass) have a cost of 2.0.

ORIGIN     |
   |       |
   |  <====|====== dirt road
   |       |
   |       |
   |       |  <=== paved road
   |       |
   |       |
   |       |
   |       |
   |       |
   |       |
   |       |
   |       |
   |       |
   |       |
   |       |
   |     TARGET

Dijkstra’s yielded path will follow the paved road. (takes a long time to compute)
A*'s yielded path will follow the dirt road. (takes a fraction of the time to compute)

I think we agree, though… :point:

[TehJavaDev]

I’m just going to use this pathfinding library instead of trying to create my first implementation of pathfinding on my own lol. (Burnt me out)

That’ll be my project today Don’t feel like swapping my game project out because I can’t create a decent pathfinding system yet haha

Thanks for everyone’s help

[Jono]

@Riven

(Near)zero-cost is not required, the effect is already observable if we have a parallel dirt road and paved road. Let’s say the edges of the dirt road have cost 1.1 and the paved road has cost 0.9, all other edges (grass) have a cost of 2.0.

Hmm… actually I think we’re in disagreement on this bit. The heuristic distance I’d use is Manhattan0.9, because the most optimistic estimate of the distance is that there is some direct path by paved road. A using this will expand more nodes than if it used un-weighted Manhattan distance but it will be optimal again.

Regardless, at least the OP decided on a solution in the meantime ;D