Astar pathfinding diagonal support

Game Mechanics
#1

this is what the path looks like
I want it to look like this http://prntscr.com/63eo9b
while keeping diagonals when there are no blocked tiles. like this http://prntscr.com/63eon5

Sorry for the vague description

#2

if that means that you want tiles always to be connected by their sides - you might want to look into bresenham’s line :

and continue with super-cover :

#3

Simply remove the edges you deem impassible: for every diagonal edge verify that it touches/intersects 4 empty cells.

basil_: bresenham seems an odd choice for his specific request (conditional diagonal edges) as it solves quite a few problems, but more or less would make his problem worse :slight_smile:

#4

yea, don’t listen to me. i’m way off most time anyway :wink:

#5

I’ll try that Riven ;D

#6

I’m struggling to do this :S
Would be very grateful if somebody could help me with it.

this code is used to check if its a solid tile.


if (MapManager.isBlocked(x,y)) {
this tile is clipped
}


public Node[] getNeighbors(Node goal) {
		Node[] neighbors = new Node[8];
		int count = 0;
		for (int i = -1; i < 2; i++) {
			for (int j = -1; j < 2; j++) {
				if (i == 0 && j == 0)
					continue;
				Node node = new Node(x + i, y + j, this);
				node.cost = node.distance(this);
				node.heuristic = node.heuristic(goal);
				neighbors[count++] = node;

			}
		}
		return neighbors;
	}
#7

if both i and h are not zero, you’re dealing with a diagonal edge to a neighbour. in that case, check whether there is any blocked cell in the 3 cells the edge is pointing to. if so, don’t add the node to the neighbour array.

#8

How would I do this exactly?

#9

the coords of the three cells:
(x+i, y+j)
(x+i, y)
(x, y+j)

#10

It’s avoiding some tiles when not needed

public Node[] getNeighbors(Node goal) {
		Node[] neighbors = new Node[8];
		int count = 0;
		for (int i = -1; i < 2; i++) {
			for (int j = -1; j < 2; j++) {
				if (i == 0 && j == 0)
					continue;
				if (i != 0 && j != 0) {
					if (!MapManager.isWalkable(x + i, y + j)
							|| !MapManager.isWalkable(x + i, y)
							|| !MapManager.isWalkable(x, y + j)) {
						System.out
								.println("diagonal tile not touching 4 empty tiles");
						break;
					}
				}
				Node node = new Node(x + i, y + j, this);
				node.cost = node.distance(this);
				node.heuristic = node.heuristic(goal);
				neighbors[count++] = node;
			}
		}
		return neighbors;
	}
#11

should be walking across the green path, http://prntscr.com/63hpd3

#12

change line 14 to: continue

#13

to wrap it up, rename i to dx, j to dy, and change the conditions to: <= +1, instead of < 2, to add meaning to the code.

#14

Yes! it’s working thank you so much!