Simple Pathfinding
by Westy · 12/18/2003 (11:49 am) · 4 comments
For AI Players.This idea would need a method of checking for collision in 4 directions at an awareness distance from the actual player(Norh,East,South,West), maybe with a castray?.
int bots; //number of bots
int awareness; //Define an awareness radius (distance of
//castray possibly?)
float avoid; //amount to move away from imminent collision i.e -1
for(b=0;b<bots;b++) //loop through each bot
{
for(w=0;w<awareness;w++) //awareness on left
{
if("castRay w distance out to left collides with anything")
{
velocty to west +=avoid; //move east faster
//turn w degrees right too?
}
}
for(n=0;n<awareness;n++) //awareness in front
{
if("castRay n distance in front collides with anything")
{
forward velocity +=avoid; //slow down
//turn n degrees left or right too?
}
}
for(e=0;e<awareness;e++) //awareness on right
{
if("castRay e distance out to right collides with anything")
{
velocty to east +=avoid; //move west faster
//turn e degrees left too?
}
}
for(s=0;s<awareness;s++) //awareness behind
{
if("castRay s distance behind collides with anything")
{
forwards velocity -=avoid; //move forward faster
}
}
}
#2
12/19/2003 (5:26 am)
The idea of this wasnt really to determine a path, but used in conjunction with waypoints to avoid running into walls forever.
#3
If your playing field is an open area (no interiors or really maze like areas) and you don't need perfect pathfinding (bots bumping into rocks ala ThinkTanks actually adds to the character of the bots) then this is a very efficient way to go. It can also be combined with waypoints, as Westy suggests.
12/19/2003 (10:37 am)
Actually, what Westy suggests is a known and good heuristic for pathfinding. We use a similar system in our tank game ThinkTanks. Instead of using ray casts, though, we do an area search. This is more efficient and more reliable (no worry about missing an obstacle to the NW, for example). After collecting a list of nearby obstacles, we then apply an "impulse" to the navigation direction for each obstacle, depending on how close that obstacle is. Basically, think of the obstacles as having negative gravity.If your playing field is an open area (no interiors or really maze like areas) and you don't need perfect pathfinding (bots bumping into rocks ala ThinkTanks actually adds to the character of the bots) then this is a very efficient way to go. It can also be combined with waypoints, as Westy suggests.
#4
01/02/2004 (4:32 am)
Ok, so it's not really "pathfinding" per-se, is it? "Antigravity" as you describe it is also a well known evasion method in the game Robocode, where enemy bullets make the robot being "pushed away" to avoid a hit. It's very effective if you don't have complex obstacles. It's *very* good when actually used only for evasion. I figure that this can be useful for having bots evade a thrown grenade or similar. 
Torque Owner Josef Jahn
Using raycasts to determine whether a bot can go somewhere isn't really feasible. You could go the Quake3-approach and analyze the BSP and terrain in a pre-processing step to produce "walkability"-data, but IMHO waypoints still yield the best results at the least amount of effort. You may want to check out my resource link above, it's ready-to-use script code that you can just pop in to your project and have working bot navigation right away.