Pathfinding

Introduction

Download the .java file

This pathfinding program implements A* in an efficient enough manner to be used for games. Here is a demonstration of it finding the shortest path between two points. The gray area are all the cells that it has explored while looking for the destination. The black squares are the wall obstacles.

Levels of Diagonalization

When dealing with square cells, making an L-shape around a corner, takes just as many moves, as taking the hypotenuse, since the hypotenuse will be created out of zig-zagging shapes. Going up,up,up,right,right,right takes the same amount of moves as going up,right,up,right,up,right. Although both are valid shortest paths, one of them just seems more correct than the other, that's why I altered my algorithm for handling diagonal movements in different ways.

This is the default movement. Due to the systematic thinking of computers, it has chosen the L shape as the preferred shortest path.

This is the first variant of diagonalization. It can make diagonal movements, but treats them as a cost of root 2. It then fills in between diagonal movements, so that the final path is made up of only up, down, left, and right. This is ideal for some tile based games.

If your game allows diagonal movement, this one is the best option. It only fills in the diagonals while going around corners so that the object won't clip the corner while moving.

This is the most lenient movement, it doesn't fill in any diagonals so that the path is the most simple.

back to projects...