Pathing

[alkatran]

Lately I've been trying to create a good pathing code... well good for a intermediate-beginner..

Anyways, what I'm going on is something like this:

Instead of active pathing (constantly calculating) I just get the path at start and save it in a string, excepting when a unit gets in way, then I make a "subpath" around it.

The order would be something similar to:

*I'm using a tile system, any tile with value above X is impassable
*The unit's can move in 8 directions

-Set terrain (temporarily) to show unit has already stepped there
-start loop here
-Get angle from unit to destination, round off to nearest 45.
-start a for loop for checking movement
-Check if tile at x+int(sin(angle)+.5),y+int(sin(angle)+.5) is passable
*-If passable then move, set terrain to show unit has been here, add to string
*-If not passable then start rotating check around (if it started at 0, it would then check 45, 315, 90, 270 etc), exit for
-end for loop
-If variable of for loop is greater then 315 then back up, look for new path
-If you back up so much your back at starting point, then you can't reach, don't bother moving.
-End loop
**-Subpath between some points to check if path can be shortened

Is this a very efficient system? Or is there a better way?

[Zaei]

The industry standard algorithm for pathfinding is the A* (A Star) algorithm. A couple of google searches should turn up some usable pseudocode for you. However, the VB implementation is likely to be hellish, and you wont find any actual code, as the implementation is really very specific to the game itself.

Z.

[alkatran]

http://www.gameai.com/antraces.html

This one was really interesting for anyone else who wants to learn about it.. Take every possible route until you reach your destination

[NoteMe]

Look at this page...there is an introduction to pathfinding using A*...

http://www.advantage.co.nz/ur/

[alkatran]

I've finished most of it... it's in QBasic though, so some commands won't work in VB.

DECLARE SUB PathMove (x!, y!, Speed!, Direction!)
DECLARE FUNCTION CoSng! (x AS STRING)
DECLARE FUNCTION Deg! (x!)
DECLARE FUNCTION Arcsin! (x!)
DECLARE FUNCTION Rad! (x!)
DECLARE FUNCTION CoStr$ (x!)
DECLARE FUNCTION Target! (SourceX!, SourceY!, DestX!, DestY!)
CONST PI = 3.141592654#
COMMON SHARED GameSpeed AS SINGLE
GameSpeed = 1
SCREEN 13
DIM TerStat(-1 TO 20, -1 TO 12)
DIM Path AS STRING
DIM TempString AS STRING
DIM SubPath AS STRING
RANDOMIZE TIMER
1
 
FOR a = 0 TO 19
 FOR b = 0 TO 11
  IF INT(RND * 4) THEN TerStat(a, b) = 0 ELSE TerStat(a, b) = 1
  LINE (a * 16, b * 16)-(a * 16 + 15, b * 16 + 15), TerStat(a, b), BF
 NEXT b
NEXT a
 
'Set impassable border around map to stop out-of-bounds
a = -1
FOR b = -1 TO 12
TerStat(a, b) = 1
NEXT b
a = 20
FOR b = -1 TO 12
TerStat(a, b) = 1
NEXT b
b = -1
FOR a = -1 TO 20
TerStat(a, b) = 1
NEXT a
b = 12
FOR a = 0 TO 19
TerStat(a, b) = 1
NEXT a
 
x = INT(RND * 19)
y = INT(RND * 11)
Dx = INT(RND * 19)
Dy = INT(RND * 11)
 
Tx = x
Ty = y
LINE (Tx * 16, Ty * 16)-(Tx * 16 + 15, Ty * 16 + 15), 14, BF
LINE (Dx * 16 + 5, Dy * 16 + 5)-(Dx * 16 + 10, Dy * 16 + 10), 4, BF
 
GOSUB FindPath
 
FOR a = 1 TO LEN(Path)
Angle = CoSng(MID$(Path, a, 1)) * 45
CALL PathMove(x, y, 1, Angle)
NEXT a
 
Path = 
 
CLS
GOTO 1
 
 
FindPath:
 TerStat(Tx, Ty) = TerStat(Tx, Ty) + 8
 IF TerStat(Dx, Dy) > 0 THEN
  FOR Increase = 0 TO 5
   FOR a = Dx - Increase TO Dx + Increase
    FOR b = Dy - Increase TO Dy + Increase
     LINE (a * 16 + 5, b * 16 + 5)-(a * 16 + 10, b * 16 + 10), 4, BF
     IF a < 20 AND a > -1 AND b < 12 AND b > -1 THEN IF TerStat(a, b) = 0 THEN Dx = a: Dy = b: GOTO FoundSpot
    NEXT b
   NEXT a
  NEXT Increase
 END IF
FoundSpot:
 DO UNTIL INKEY$ = CHR$(27)
  Angle = INT(Target(Tx, Ty, Dx, Dy) / 45) * 45
  FOR r = 0 TO 10000
   IF INKEY$ = CHR$(27) THEN END
  NEXT r
  FOR Increase = 45 TO 315 STEP 45
   IF TerStat(Tx + INT(SIN(Rad(Angle)) + .5), Ty + INT(COS(Rad(Angle)) + .5)) < 1 THEN
    CALL PathMove(Tx, Ty, 1, Angle)
    TerStat(Tx, Ty) = TerStat(Tx, Ty) + 8
    Path = Path + CoStr$(Angle / 45)
    LINE (Tx * 16, Ty * 16)-(Tx * 16 + 15, Ty * 16 + 15), 12, BF
    IF Tx = Dx AND Ty = Dy THEN EXIT DO
    EXIT FOR
   ELSE
    IF UpDown = 0 THEN Angle = Angle + Increase: UpDown = 1 ELSE Angle = Angle - Increase: UpDown = 0
   END IF
  NEXT Increase
  IF Increase = 360 AND Tx = x AND Ty = y THEN Path = 
: EXIT DO
  IF Increase = 360 THEN LINE (Tx * 16, Ty * 16)-(Tx * 16 + 15, Ty * 16 + 15), 2, BF: Angle = CoSng(RIGHT$(Path, 1)) * 45 + 180: CALL PathMove(Tx, Ty, 1, Angle): Path = LEFT$(Path, LEN(Path) - 1)
 LOOP
 GOSUB ShortenPath
 GOSUB ClearFootPrints
RETURN
 
 
FindSubPath:
 TerStat(Tx, Ty) = TerStat(Tx, Ty) + 8
 DO UNTIL INKEY$ = CHR$(27)
  Angle = INT(Target(Tx, Ty, Dx, Dy) / 45) * 45
  FOR a = 0 TO 25000
  NEXT a
  FOR Increase = 45 TO 315 STEP 45
   IF TerStat(Tx + INT(SIN(Rad(Angle)) + .5), Ty + INT(COS(Rad(Angle)) + .5)) < 1 THEN
    CALL PathMove(Tx, Ty, 1, Angle)
    TerStat(Tx, Ty) = TerStat(Tx, Ty) + 8
    SubPath = SubPath + CoStr$(Angle / 45)
    LINE (Tx * 16, Ty * 16)-(Tx * 16 + 15, Ty * 16 + 15), 12, BF
    IF Tx = Dx AND Ty = Dy THEN EXIT DO
    EXIT FOR
   ELSE
    IF UpDown = 0 THEN Angle = Angle + Increase: UpDown = 1 ELSE Angle = Angle - Increase: UpDown = 0
   END IF
  NEXT Increase
  IF Increase = 360 AND Tx = x AND Ty = y THEN SubPath = 
: EXIT DO
  IF Increase = 360 THEN Angle = CoSng(RIGHT$(SubPath, 1)) * 45 + 180: CALL PathMove(Tx, Ty, 1, Angle): SubPath = LEFT$(SubPath, LEN(SubPath) - 1)
 LOOP
 Path = LEFT$(Path, ShortStart) + SubPath + RIGHT$(Path, 0 + SubPathStart + LEN(SubPath))
 GOSUB ClearFootPrints
RETURN
 
 
ShortenPath:
 ShortJump = 2
 FOR a = 1 TO LEN(Path)
  ShortStart = a
  TempString = Path
  FOR b = 1 TO ShortJump
   Angle = CoSng(MID$(Path, b, 1)) * 45
   CALL PathMove(x, y, 1, Angle)
  NEXT b
  Path = TempString
  Tx = x: Ty = y
  GOSUB FindSubPath
 NEXT a
RETURN
 
 
FollowPath:
 IF TerStat(x + INT(SIN(Rad(Angle)) + .5), y + INT(COS(Rad(Angle)) + .5)) < 1 THEN
  Angle = CoSng(LEFT$(Path, 1)) * 45
  CALL PathMove(x, y, 1, Angle)
  Path = RIGHT$(Path, LEN(Path) - 1)
 ELSE
  Dx = x + CoSng(MID$(Path, 1, 1)) * 45
  Dy = y + CoSng(MID$(Path, 1, 1)) * 45
  Dx = Dx + CoSng(MID$(Path, 2, 1)) * 45
  Dy = Dy + CoSng(MID$(Path, 2, 1)) * 45
  Tx = x: Ty = y
  ShortStart = 0
  GOTO FindSubPath
 END IF
RETURN
 
 
ClearFootPrints:
 FOR a = 0 TO 19
  FOR b = 0 TO 11
   IF TerStat(a, b) >= 8 THEN TerStat(a, b) = TerStat(a, b) - 8
  NEXT b
 NEXT a
RETURN
 
FUNCTION Arcsin (x)
IF SQR(-x * x + 1) = 0 THEN EXIT FUNCTION
x = ATN(x / SQR(-x * x + 1))
Arcsin = Deg(x)
END FUNCTION
 
FUNCTION CoSng (x AS STRING)
IF x = 
0
 THEN CoSng = 0
 
IF x = 
1
 THEN CoSng = 1
IF x = 
2
 THEN CoSng = 2
IF x = 
3
 THEN CoSng = 3
IF x = 
4
 THEN CoSng = 4
IF x = 
5
 THEN CoSng = 5
IF x = 
6
 THEN CoSng = 6
IF x = 
7
 THEN CoSng = 7
IF x = 
8
 THEN CoSng = 8
END FUNCTION
 
FUNCTION CoStr$ (x)
IF x > 16 THEN x = x - 16
IF x > 8 THEN x = x - 8
IF x < 0 THEN x = x + 8
IF x < -8 THEN x = x + 16
IF x = 0 THEN CoStr = 
0
 
IF x = 1 THEN CoStr = 
1
 
IF x = 2 THEN CoStr = 
2
 
IF x = 3 THEN CoStr = 
3
 
IF x = 4 THEN CoStr = 
4
 
IF x = 5 THEN CoStr = 
5
 
IF x = 6 THEN CoStr = 
6
 
IF x = 7 THEN CoStr = 
7
 
IF x = 8 THEN CoStr = 
8
 
END FUNCTION
 
FUNCTION Deg (x)
Deg = x * (180 / PI)
END FUNCTION
 
SUB PathMove (x, y, Speed, Direction)
x = x + (Speed * GameSpeed) * INT(SIN(Rad(Direction)) + .5)
y = y + (Speed * GameSpeed) * INT(COS(Rad(Direction)) + .5)
END SUB
 
FUNCTION Rad (x)
Rad = x * (PI / 180)
END FUNCTION
 
FUNCTION Target (SourceX, SourceY, DestX, DestY)
DIM Vertical AS SINGLE
DIM Horizontal AS SINGLE
DIM Diagonal AS SINGLE
DIM Vector AS SINGLE
Horizontal = ABS(SourceX - DestX)
Vertical = ABS(SourceY - DestY)
IF Horizontal AND Vertical <> 0 THEN
 Diagonal = SQR((Horizontal ^ 2) + (Vertical ^ 2))
 Vector = (Arcsin(Vertical / Diagonal))
 IF DestX > SourceX AND DestY > SourceY THEN Vector = 0 - Vector: Vector = Vector + 90
 IF DestX > SourceX AND DestY < SourceY THEN Vector = Vector + 90
 IF DestX < SourceX AND DestY > SourceY THEN Vector = Vector + 270
 IF DestX < SourceX AND DestY < SourceY THEN Vector = 180 - Vector: Vector = Vector + 90
ELSE
 IF Horizontal = 0 AND DestY > SourceY THEN Vector = 0
 IF Horizontal = 0 AND DestY < SourceY THEN Vector = 180
 IF Vertical = 0 AND DestX > SourceX THEN Vector = 90
 IF Vertical = 0 AND DestX < SourceX THEN Vector = 270
 IF Vertical = 0 AND Horizontal = 0 THEN Vector = 0: Target = 0: EXIT FUNCTION
END IF
DO UNTIL Vector <= 360 AND Vector > 0
 IF Vector <= 0 THEN Vector = Vector + 360
 IF Vector > 360 THEN Vector = Vector - 360
LOOP
Target = Vector
END FUNCTION