BASIC 中使用BEST-FIRST 搜索路径
来自:http://member.netease.com/~ldx/index.htm 作者:凌云RTC
 在网上看了一些讲AI的资料,对搜索路径很感兴趣(因为有了这个,在游戏中就可以用鼠标指挥
了),但我看过的资料中全是C++的程序(唉,可怜我们BASIC 没那么多数据类型),想想我钟情的
BASIC,便决定要写BASIC 的程序.一下午写了出来,用的是 BEST-FIRST 算法(不过我也不知这算
不算是),给大家看一下:
说明:
本程序中估价使用的是 评价值=|终止节点X-当前节点X|+|终止节点Y-当前节点Y|
注:
算法说明可以从各大游戏制作站点的技术文档中关于AI的文章中找到.

DECLARE SUB PathFind (N AS ANY, T AS ANY, PathFound() AS ANY, PathNumber AS INTEGER)
DECLARE FUNCTION SelDirect! ()
DECLARE SUB SelNode (SeledNode AS ANY, Col AS INTEGER)

'$DYNAMIC '使用动态数组
'DEFINT A-Z '缺省时全部变量使用整型

CLS : SCREEN 13 '进入图形方式
TYPE Node '定义新类型---节点
x AS INTEGER
y AS INTEGER
END TYPE

DIM SHARED Maze(33, 21) '定义障碍数组

DIM SHARED N AS Node, T AS Node '定义节点
DIM xww AS Node, LASTN AS Node
DIM PathFound(0) AS Node, PathNumber AS INTEGER '定义路径表 及 路径表中包含的节点数
FOR j = 0 TO 19
FOR i = 0 TO 31
READ w '读入障碍数据
Maze(i, j) = w
IF w = 1 THEN LINE (i * 10, j * 10)-(i * 10 + 9, j * 10 + 9), 4, BF
NEXT
NEXT

SelNode N, 2 '选择初始节点
SelNode T, 3 '选择终止节点


LINE (T.x, T.y)-(T.x + 9, T.y + 9), 3, BF

PathFind N, T, PathFound(), PathNumber '生成从N节点到T节点的路径

FOR i = 0 TO PathNumber - 1 '显示已生成的路径
LINE (PathFound(i).x, PathFound(i).y)-(PathFound(i).x + 9, PathFound(i).y + 9), 2, BF
NEXT

'障碍数据
DATA 0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
DATA 0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
DATA 0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
DATA 0,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
DATA 0,0,0,1,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
DATA 0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
DATA 0,0,1,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
DATA 0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
DATA 0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
DATA 0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0


SUB PathFind (N AS Node, T AS Node, PathFound() AS Node, PathNumber AS INTEGER)
'估测路径表中节点数
PathNumber = 2 * INT(ABS(T.x / 10 - N.x / 10) + ABS(T.y / 10 - N.y / 10)) + 10
DIM LASTN1 AS Node, LASTN AS Node
REDIM PathFound(PathNumber) AS Node
PathFound(0).x = N.x
PathFound(0).y = N.y
PathNumber = 1

IF Maze((T.x / 10), INT(T.y / 10)) <> 1 THEN '如果终止节点不是障碍,则

DO UNTIL (N.x = T.x AND N.y = T.y) '循环直到到达目标节点

RNDDirect = SelDirect '选择方向
SELECT CASE RNDDirect
CASE 1 '上
N.x = N.x: N.y = N.y - 10
CASE 2 '右
N.x = N.x + 10: N.y = N.y
CASE 3 '下
N.x = N.x: N.y = N.y + 10
CASE 4 '左
N.x = N.x - 10: N.y = N.y
END SELECT

IF ((LASTN1.x = N.x) AND (LASTN1.y = N.y)) OR ((LASTN.x = N.x) AND (LASTN.y = N.y)) THEN
REP = REP + 1 '
IF REP > 5 THEN EXIT DO '如果重复到达同一节点则停止
END IF
LASTN1.x = LASTN.x: LASTN1.y = LASTN.y '记下上次及上上次访问的节点
LASTN.x = N.x: LASTN.y = N.y
PathFound(PathNumber).x = N.x
PathFound(PathNumber).y = N.y
PathNumber = PathNumber + 1
LOOP
ELSE
PRINT "T is a bar"
END IF
END SUB

FUNCTION SelDirect
DIM s(4) AS INTEGER

IF Maze(INT(N.x / 10), INT((N.y - 10) / 10)) = 0 THEN
s(1) = ABS(T.x / 10 - N.x / 10) + ABS(T.y / 10 - N.y / 10 + 1)
ELSE
s(1) = -1
END IF


IF Maze(INT((N.x + 10) / 10), INT(N.y / 10)) = 0 THEN
s(2) = ABS(T.x / 10 - N.x / 10 - 1) + ABS(T.y / 10 - N.y / 10)
ELSE
s(2) = -1
END IF

IF Maze(INT(N.x / 10), INT((N.y + 10) / 10)) = 0 THEN
s(3) = ABS(T.x / 10 - N.x / 10) + ABS(T.y / 10 - N.y / 10 - 1)
ELSE
s(3) = -1
END IF


IF Maze(INT((N.x - 10) / 10), INT(N.y / 10)) = 0 THEN
s(4) = ABS(T.x / 10 - N.x / 10 + 1) + ABS(T.y / 10 - N.y / 10)
ELSE
s(4) = -1
END IF

FOR i = 1 TO 4
IF s(i) <> -1 THEN MIN = s(i): FX = i: EXIT FOR
NEXT
IF (s(1) = -1) AND (s(2) = -1) AND (s(3) = -1) AND (s(4) = -1) THEN
FX = 0
ELSE
FOR i = 1 TO 4
IF s(i) <> -1 THEN
IF s(i) < MIN THEN MIN = s(i): FX = i
END IF
NEXT
END IF
SelDirect = FX
END FUNCTION

DEFINT A-Z
SUB SelNode (SeledNode AS Node, Col AS INTEGER)
'CLS
DIM TEMP(100) AS INTEGER
GET (0, 0)-(9, 9), TEMP
DO
SELECT CASE INKEY$
CASE "8"
NewX = LastX: NewY = LastY - 10
IF NewY < 0 THEN NewY = 0
PUT (LastX, LastY), TEMP, PSET
GET (NewX, NewY)-(NewX + 9, NewY + 9), TEMP
LINE (NewX, NewY)-(NewX + 9, NewY + 9), Col, B
LastX = NewX: LastY = NewY
CASE "5"
NewX = LastX: NewY = LastY + 10
IF NewY > 190 THEN NewY = 190
PUT (LastX, LastY), TEMP, PSET
GET (NewX, NewY)-(NewX + 9, NewY + 9), TEMP
LINE (NewX, NewY)-(NewX + 9, NewY + 9), Col, B
LastX = NewX: LastY = NewY
CASE "4"
NewX = LastX - 10: NewY = LastY
IF NewX < 0 THEN NewX = 0
PUT (LastX, LastY), TEMP, PSET
GET (NewX, NewY)-(NewX + 9, NewY + 9), TEMP
LINE (NewX, NewY)-(NewX + 9, NewY + 9), Col, B
LastX = NewX: LastY = NewY
CASE "6"
NewX = LastX + 10: NewY = LastY
IF NewX > 310 THEN NewX = 310
PUT (LastX, LastY), TEMP, PSET
GET (NewX, NewY)-(NewX + 9, NewY + 9), TEMP
LINE (NewX, NewY)-(NewX + 9, NewY + 9), Col, B
LastX = NewX: LastY = NewY
CASE CHR$(13)
PUT (LastX, LastY), TEMP, PSET
ExitFlag = 1
END SELECT


LOOP UNTIL ExitFlag = 1
SeledNode.x = NewX: SeledNode.y = NewY
END SUB