AI Pathfinding> Go Here

[Agamemnus]

The aim of this topic is to try to show anyone interested how to write a pathfinding program.

The code is at the bottom, and now follows a description of the code.

Input Description:

Code:

DIM SHARED x2b(4) as integer, y2b(4) as integer
x2b(1) = 1: y2b(1) = 0
x2b(2) = -1: y2b(2) = 0
x2b(3) = 0: y2b(3) = 1
x2b(4) = 0: y2b(4) = -1

SUB smart.move (x0 AS INTEGER, y0 AS INTEGER, x1 AS INTEGER, y1 AS INTEGER, array1() AS INTEGER, iteration.max AS INTEGER)

The first part defines adjacent x/y coordinates.

Smart.move takes (x0, y0) and (x1, y1) for the target and source points on array1(), the X, Y grid.

Array1() contains wall locations for the source. The source cannot go in those places. Wall locations are places in array1() greater than zero.

Iteration.max gives the theoretical maximum target places that the source can go to, including the source position itself.

Code:

IF array1(x0, y0) > 0 THEN random.move: EXIT SUB

says that any unreachable target (any target located on a wall) cannot be reached. Therefore move randomly.

Code:

DIM temp(1 TO x.max%, 1 TO y.max%) AS INTEGER
DIM path.x(1 TO max.spaces) AS INTEGER
DIM path.y(1 TO max.spaces) AS INTEGER
DIM i AS INTEGER, j AS INTEGER, k AS INTEGER, h AS INTEGER, exitloop AS INTEGER

Imagine, gentlemen, a black square. The target is the upper-right, and the source is the center. In the center, there is a bright white light. For each pixel next to the center, the brightness decreases by one and the darkness increases by one. This way the whole map is filled. "temp" holds this darkness.

x.max and y.max are the upper bounds of array1() [they are globals..]
It is worth noting at this stage that the extreme limits of array1() are enclosed by borders, to prevent the pathfinding mechanism from going out of bound.

path.x and path.y hold all the current pixels to be checked. They, as well as the rest of the variables, will be explained later.

Code:

path.x(1) = x0
path.y(1) = y0
endk = 1
temp(x0, y0) = 1
DO
IF h = iteration.max THEN random.move: EXIT SUB
h = h + 1
DO
IF i = iteration.max THEN i = 1 ELSE i = i + 1
x% = path.x(i)
y% = path.y(i)
FOR j = 1 TO 4
x2% = x% + x2b(j)
y2% = y% + y2b(j)
IF temp(x2%, y2%) <> 0 THEN GOTO contj1
IF array1(x2%, y2%) <> 0 THEN GOTO contj1
IF k = iteration.max THEN k = 1 ELSE k = k + 1
path.x(k) = x2%
path.y(k) = y2%
temp(x2%, y2%) = h + 1
IF x1% = x2% THEN IF y1% = y2% THEN exitloop = 1: EXIT DO
contj1:
NEXT j
IF i = endk THEN EXIT DO
LOOP
endk = k
i = i - 1
LOOP UNTIL exitloop = 1

This is the hard part to understand. What it does is:

1a) if the iteration.max has not been reached, then go through all the current (path.x(), path.y()) points.
1b) if it has, exit out and perform a random move.
2) for each point,
a) check whether there is an adjacent, non-wall point in the (x2b(), y2b()) direction.
b) check whether that point hasn't been painted already in the temp() array.
c) if both conditions apply, paint the point with one increase "in darkness" in the temp() array.
d) if the point is the target point, exit out of the loop.
3) start looping through the points with the first new point at (1).

The point that touches the target point is the point that is returned:

Code:

ghostrow(cur.ghost%) = y
ghostcol(cur.ghost%) = x
ERASE path.x, path.y, temp

So how does this get the answer? Well, the target is actually the unit you want to move, and the source is the unit you want to move to. Annoying, I know.

Ok, does anyone understand me?!?!

This can get a little more complicated if you want to generate a full path right away, and a lot more hairy if each tile actually varies in distance cost, and a bit more complicated if you start with two light sources. (shortens the amount of time the algorithm runs)

Code:

DIM SHARED x2b(4) as integer, y2b(4) as integer
x2b(1) = 1: y2b(1) = 0
x2b(2) = -1: y2b(2) = 0
x2b(3) = 0: y2b(3) = 1
x2b(4) = 0: y2b(4) = -1

SUB smart.move (x0 AS INTEGER, y0 AS INTEGER, x1 AS INTEGER, y1 AS INTEGER, array1() AS INTEGER, iteration.max AS INTEGER)

IF array1(x0, y0) > 0 THEN random.move: EXIT SUB

DIM temp(1 TO x.max%, 1 TO y.max%) AS INTEGER
DIM path.x(1 TO max.spaces) AS INTEGER
DIM path.y(1 TO max.spaces) AS INTEGER
DIM i AS INTEGER, j AS INTEGER, k AS INTEGER, h AS INTEGER, exitloop AS INTEGER, endk AS INTEGER
path.x(1) = x0
path.y(1) = y0
endk = 1
temp(x0, y0) = 1

DO
IF h = iteration.max THEN random.move: EXIT SUB
h = h + 1
DO
IF i = iteration.max THEN i = 1 ELSE i = i + 1
x% = path.x(i)
y% = path.y(i)
FOR j = 1 TO 4
x2% = x% + x2b(j)
y2% = y% + y2b(j)
IF temp(x2%, y2%) <> 0 THEN GOTO contj1
IF array1(x2%, y2%) <> 0 THEN GOTO contj1
IF k = iteration.max THEN k = 1 ELSE k = k + 1
path.x(k) = x2%
path.y(k) = y2%
temp(x2%, y2%) = h + 1
IF x1% = x2% THEN IF y1% = y2% THEN exitloop = 1: EXIT DO
contj1:
NEXT j
IF i = endk THEN EXIT DO
LOOP
endk = k
i = i - 1
LOOP UNTIL exitloop = 1

ghostrow(cur.ghost%) = y
ghostcol(cur.ghost%) = x
ERASE path.x, path.y, temp
END SUB

[Agamemnus]

no comments...? :|

[Hard Rock]

No Double Posts. Please.

I havn't tried your code, but if it works, then why not submit it as a qbnews article? And if it works then: (i havnt really read it yet either busy)

But here, ill save this page for future referece.

[Agamemnus]

I want to see if people understand me or if people don't or if people do, just a little, so I can make it readable.

[na_th_an]

Well, I *can* read it, but I am more used to indented code. So you know what I'll be arguing

Nice work man. This is material for an article at our beloved FAQ

[Agamemnus]

I'll rewrite it tomorrow, with images and GIFs!

[relsoft]

Be sure you do since it wont run on my system. ;*(

[Agamemnus]

What do you mean, won't run? Loops forever? Did you add in the border tiles?

----delay of one day------