I just started to actively use the pathfinding algorithm 
I got some code that works just as I wanted to small maps, however as the map grew, the pathfinder just kind of gives up?
Any help would be appreciated.
Here is how it fails:
Pathfinder class
See below.
CopyableCougar4
I think it fails once either the active tile x or active tile y are the target, not when BOTH are the target.
CopyableCougar4
ITile left = map.getTile(ax - 1, ay);
left.setParent(active);
ITile right = map.getTile(ax - 1, ay);
right.setParent(active);
2 times ax -1
Thanks for that
Here is the updated Pathfinder class:
EDIT: see below.
CopyableCougar4
However, the code still seems to fail the same 
CopyableCougar4
It’s a very simple issue to do with your ‘while’ loop.
Take a look at the documentation (And especially practice your truth tables), but basically you’re loop is saying:
ax != tx && ay != ty which is equivalent to !(ax == tx || ay == ty). This causes it to stop too soon.
!(ax == tx && ay == ty) is what you wanted.
Edit: Basically, notting a composite statement ( X && Y) is not the same as doing !X && !Y.
I think you found my issue UprightPath Still cleaning up some null values, but thanks
CopyableCougar4
Update: So I fixed those issues, but now it keeps getting hung up in the pathfinding at 0,0…
Pathfinder class. Again.
See below
CopyableCougar4
private double F(int sx, int sy, int tx, int ty, int ax, int ay){
if(ax < 0 || ay < 0 || ay >= map.getHeight() || ax >= map.getWidth()){
return 1000;
}
double G = Math.sqrt((double)(ax - sx) * (double)(ax - sx) + (double)(ay - sy) * (double)(ay - sy));
double H = (double)(tx - ax) + (double)(ty - ay);
double F = G + H;
return map.getTile(ax, ay).weight * F; // Multiply by the weight of the tile
}
can you try this,
maybe your path looks more direct then.
The path still gets hung up
CopyableCougar4
Also, what you’re currently doing is not an A* Search algorithm. It’s a heuristic Depth First Search. The difference being you’re only checking the children of your current not to see which should be next to be visited. In an A* (Or other list-based algorithms) you make use of the ‘open list’ (A list sorted based off of the node’s F value) to find your next candidate for expansion.
Further, your path’s going to be very wonky because it’s not actually keeping track of the best path. It’s just keeping track of expansion order.
As for the current issue? Print out the expansion order and check of tx and ty are ever reached. It might be that this call: check(min, tile) && available(tile) is either failing or being overwritten by a subsequent call (IE- the tile that would get you to [tx, ty] is NOT the last expansion node (bottomRight) but the bottomRight evaluates that call to true.)
Well that makes me feel quite stupid. I will retract into my cave until I am actually using A*…
CopyableCougar4
I’ll post this again just because it is so good, and maybe you haven’t seen it: http://www.redblobgames.com/pathfinding/a-star/introduction.html
All pictures are interactive!
Cool website, thanks for posting
So I think I am closer to actual A* pathfinding. However, you can see the current path in the image below
Pathfinder code:
public class Pathfinder {
private TileMap map;
public Pathfinder(TileMap map){
this.map = map;
}
private ArrayList<ITile> open = new ArrayList<ITile>();
private ArrayList<ITile> closed = new ArrayList<ITile>();
public Path getPath(int tx, int ty, int sx, int sy){
long before = System.currentTimeMillis();
int ax = sx, ay = sy; // active tiles
Path path = new Path();
ITile active = map.getTile(ax, ay);
open.add(active);
path.addTile(active);
while(!(ax == tx && ay == ty) || open.size() == 0){ // continue until the path has been completed or there are no possible tiles left
// Get the surrounding tiles
ITile topleft = map.getTile(ax - 1, ay - 1);
if(topleft != null) topleft.setParent(active);
ITile top = map.getTile(ax, ay - 1);
if(top != null) top.setParent(active);
ITile topright = map.getTile(ax + 1, ay - 1);
if(topright != null) topright.setParent(active);
ITile left = map.getTile(ax - 1, ay);
if(left != null) left.setParent(active);
ITile right = map.getTile(ax + 1, ay);
if(right != null) right.setParent(active);
ITile bottomleft = map.getTile(ax - 1, ay + 1);
if(bottomleft != null) bottomleft.setParent(active);
ITile bottom = map.getTile(ax, ay + 1);
if(bottom != null) bottom.setParent(active);
ITile bottomright = map.getTile(ax + 1, ay + 1);
if(bottomright != null) bottomright.setParent(active);
// Swap out the tiles
if(topleft != null && topleft.weight < 100 && available(topleft)){
open.add(topleft);
}
if(top != null && top.weight < 100 && good(top)){
open.add(top);
}
if(topright != null && topright.weight < 100 && good(topright)){
open.add(topright);
}
if(left != null && left.weight < 100 && good(left)){
open.add(left);
}
if(right != null && right.weight < 100 && good(right)){
open.add(right);
}
if(bottomleft != null && bottomleft.weight < 100 && good(bottomleft)){
open.add(bottomleft);
}
if(bottom != null && bottom.weight < 100 && good(bottom)){
open.add(bottom);
}
if(bottomright != null && bottomright.weight < 100 && good(bottomright)){
open.add(bottomright);
}
// Get their values
double topleftF = F(sx, sy, tx, ty, ax, ay);
double topF = F(sx, sy, tx, ty, ax, ay);
double toprightF = F(sx, sy, tx, ty, ax, ay);
double leftF = F(sx, sy, tx, ty, ax, ay);
double rightF = F(sx, sy, tx, ty, ax, ay);
double bottomleftF = F(sx, sy, tx, ty, ax, ay);
double bottomF = F(sx, sy, tx, ty, ax, ay);
double bottomrightF = F(sx, sy, tx, ty, ax, ay);
// Determine the lowest step
double min = min(topleftF, topF, toprightF, leftF, rightF, bottomleftF, bottomF, bottomrightF);
if(check(min, topleftF) && available(topleft)){
active = topleft;
}
else if(check(min, topF) && available(top)){
active = top;
}
else if(check(min, toprightF) && available(topright)){
active = topright;
}
else if(check(min, leftF) && available(left)){
active = left;
}
else if(check(min, rightF) && available(right)){
active = right;
}
else if(check(min, bottomleftF) && available(bottomleft)){
active = bottomleft;
}
else if(check(min, bottomF) && available(bottom)){
active = bottom;
}
else if(check(min, bottomrightF) && available(bottomright)){
active = bottomright;
}
// Remove the tiles
ax = active.tx;
ay = active.ty;
swap(active);
// Add the step
path.addTile(active);
}
// Add the target tile
path.addTile(map.getTile(tx, ty));
long after = System.currentTimeMillis();
path.setOverall(map.getTile(sx, sy), map.getTile(tx, ty));
path.setMillis(after - before);
return path;
}
// -------------[ UTILITIES ]-------------
private void swap(ITile tile){
if(tile == null) return;
open.remove(tile);
closed.add(tile);
}
private boolean good(ITile tile){
if(tile == null) return false;
return !closed.contains(tile);
}
private boolean available(ITile tile){
if(tile == null) return false;
if(!open.contains(tile)){
return false;
}
if(closed.contains(tile)){
return false;
}
return open.contains(tile) && !closed.contains(tile);
}
private boolean check(double min, double F){
return min == F;
}
private double min(double... doubles){
double min = 1000000;
for(double double_ : doubles){
min = Math.min(double_, min);
}
return min;
}
private double F(int sx, int sy, int tx, int ty, int ax, int ay){
if(ax < 0 || ay < 0 || ay >= map.getHeight() || ax >= map.getWidth()){
return 1000;
}
double G = Math.sqrt((ax - sx) * (ax - sx) + (ay - sy) * (ay - sy));
double H = Math.abs(tx - ax) + Math.abs(ty - ay);
double F = G + H;
return map.getTile(ax, ay).weight * F; // Multiply by the weight of the tile
}
}
CopyableCougar4
Your code looks a bit wonky, so I went ahead and implemented breadth first search (BFS) which is what A* is based on.
It’s just a direct translation from the link I posted, up until the “Movement Costs” section.
Feel free to run with it, I recommend continuing down the page I linked, at the end you will have full blown A*.
public static List<Tile> getPath(TileMap tileMap, Tile start, Tile goal) {
Queue<Tile> frontier = new ArrayDeque<>();
Map<Tile, Tile> cameFrom = new HashMap<>();
frontier.add(start);
cameFrom.put(start, null);
while (!frontier.isEmpty()) {
Tile current = frontier.remove();
if (current.equals(goal))
break;
for (Tile next : tileMap.neighborhood(current)) {
if (!cameFrom.containsKey(next)) {
frontier.add(next);
cameFrom.put(next, current);
}
}
}
Tile current = goal;
ArrayList<Tile> path = new ArrayList<>();
path.add(current);
while (!current.equals(start)) {
current = cameFrom.get(current);
path.add(current);
}
path.trimToSize();
return path; // list is ordered goal -> start, includes both
}
////////////////////////////////////
class Tile {
int x, y;
}
abstract class TileMap {
public abstract Tile get(int x, int y);
// add a predicate parameter to determine if a tile should be included, like isTraversable, etc
public Iterable<Tile> neighborhood(Tile tile) {
int x = tile.x;
int y = tile.y;
return Arrays.asList(get(x, y - 1), get(x, y + 1), get(x - 1, y), get(x + 1, y));
}
}
You’re getting a bit closer! And don’t worry, it’s a common mistake and all part of learning how to do these things. :3
Basically, now, you need to change your list such that it’s a sorted list (Have your Tile extend Comparable and have your comparable return the difference between the computed Fs of the tiles) and then at the start of each iteration set active = open.get(0) (That’ll ensure that you’re computing the best past).
The issue with the path that you have right now is that you’re adding each explored tile to the path (Your Path will look VERY similar to your closed list at current). You should be creating the path by backtracking down tile.parent once you’ve found your goal.
As a separate, but related note, you might also being having issues with your computation of F. Currently, the weight of the tile is being applied to the entire path when F is computed, rather than to the single node (That is to say that after it will consider a path that’s taken ‘100’ steps to get to better if the next step has a weight of 10, than a path that’s taken 50 step to get to but has a weight of 25.
Also, what BurntPizza provided in a rather good start!
I thought I had it on Sunday, but this is what I get currently:
The red is the path… the path goes to 0,0 before going to the path, which I don’t understand.
CopyableCougar4
Print out your actual path, in order, and see if it’s making any sense at all. I think that it’s currently just all of the items that have been ‘active’, not the ones that act actually part of the path.
Then do a ‘backtrack’ through your node.parent fields and see if that path makes any more sense.
This i the path.
5, 2
5, 1
5, 0
4, 0
3, 0
2, 0
1, 0
0, 0
0, 1
1, 1
2, 1
3, 1
4, 1
3, 2
2, 2
1, 2
I know it’s not printing all options because then the bottom half should also be showing.