Plan for Tom Spilman
by Tom Spilman · 04/11/2005 (7:37 pm) · 6 comments
I took this weekend off of CartShop5 exporter work to finish up the work on NPC pathfinding for our game.
So i started looking around the GG site for some decent bot pathfinding for Torque. To my disappointment i didn't find very much. I saw that the Torque AI Pack isn't going to be released for a while longer and Josef Jahn's resource was the best thing going. So that's where I decided to start.
I integrated the "AI Pathfinding" resource and got some ok initial results. It's automatic waypoint placement mode which is done by walking around the level isn't very good. Since it's triggered by line of sight it will always place a point after you turn a corner. This leaves you with a path where the AI will rub the wall to turn the corner. It was also time consuming and prone to error for an artist working with a map. Still it wasn't all bad... the pathfinding algo is fairly fast and works ok most of the time. It does break down at times and wander away from the goal, but that could be a bug I introduced.
Still I didn't like the manual point placement and wanted something fully automatic. So to improve on it I started firing rays thru the interior to see what I could get. The initial results were positive, but needed a lot more work. One week later and I'm pretty happy with what I've gotten. No wall rubbing and 100% automatically generated.
The downside is that it uses an obscene amount of points to get this level of navigation. Once I get past the prototype phase I'll look into combining these points into convex areas which will leave me with a system sort of like Counterstrike Source uses.
You can watch a little video (actually it's like 35MB) I threw together using Windows Movie Maker.
So i started looking around the GG site for some decent bot pathfinding for Torque. To my disappointment i didn't find very much. I saw that the Torque AI Pack isn't going to be released for a while longer and Josef Jahn's resource was the best thing going. So that's where I decided to start.
I integrated the "AI Pathfinding" resource and got some ok initial results. It's automatic waypoint placement mode which is done by walking around the level isn't very good. Since it's triggered by line of sight it will always place a point after you turn a corner. This leaves you with a path where the AI will rub the wall to turn the corner. It was also time consuming and prone to error for an artist working with a map. Still it wasn't all bad... the pathfinding algo is fairly fast and works ok most of the time. It does break down at times and wander away from the goal, but that could be a bug I introduced.
Still I didn't like the manual point placement and wanted something fully automatic. So to improve on it I started firing rays thru the interior to see what I could get. The initial results were positive, but needed a lot more work. One week later and I'm pretty happy with what I've gotten. No wall rubbing and 100% automatically generated.
The downside is that it uses an obscene amount of points to get this level of navigation. Once I get past the prototype phase I'll look into combining these points into convex areas which will leave me with a system sort of like Counterstrike Source uses.
You can watch a little video (actually it's like 35MB) I threw together using Windows Movie Maker.
About the author
Tom is a programmer and co-owner of Sickhead Games, LLC.
#2
I've pretty much given up on the AI Pack so seeing this got me very excited. If you're not planning on releasing this as a product, at least contact me to discuss other possibilites if you like.
By the way, is the automatic waypoint creation done once and then cached to a file sorta like lightmaps? I would guess so. Also, have you tried this outside of interiors - terrain?
Nick
04/12/2005 (6:06 am)
Give me a price! Seriously Tom, great work you've done there in so little time! I personally think that AI pathfinding is the single most important feature that is "missing" from stock TGE. Everything else is pretty manageable but I find coding pathfinding a little scary but extremely necessary (escpecially for single player games like mine).I've pretty much given up on the AI Pack so seeing this got me very excited. If you're not planning on releasing this as a product, at least contact me to discuss other possibilites if you like.
By the way, is the automatic waypoint creation done once and then cached to a file sorta like lightmaps? I would guess so. Also, have you tried this outside of interiors - terrain?
Nick
#4
04/12/2005 (6:21 am)
Great work Tom!
#5
For instance the waypoint cache file for that one map which isn't very large is 350K.... i don't see that as acceptable for most games. Also the lookup for finding a path can sometimes visit as many as 90 waypoints in the final path... that's too much for such a small interior. Imagine this same technique applied to Stronghold with more than one AI.
I still have some work to do if i plan to make it competitive to the AI pack... which really isn't my goal. In fact if the AI pack was out in the next 4 months i'll switch over to it immediately.
Now if the AI pack isn't out in the next 4 months i will be continuing to expand this code. The waypoints will be replaced by network of convex polygons. An AI can move anywhere inside these areas without concern of collision with any static geometry. Possibly a similar technique could be used for terrain ignoring slope changes under 80 degrees, but for our project terrain isn't needed.
@Tim and Michael - Thanks.
04/12/2005 (7:41 am)
@Nick - We're doing a single player game as well. I wouldn't give up on the AI pack... they have certainly put alot more time and thought into it than i have. My solution so far is only tested on interiors, and i'm sure it would scale horribly to exterior scenes.For instance the waypoint cache file for that one map which isn't very large is 350K.... i don't see that as acceptable for most games. Also the lookup for finding a path can sometimes visit as many as 90 waypoints in the final path... that's too much for such a small interior. Imagine this same technique applied to Stronghold with more than one AI.
I still have some work to do if i plan to make it competitive to the AI pack... which really isn't my goal. In fact if the AI pack was out in the next 4 months i'll switch over to it immediately.
Now if the AI pack isn't out in the next 4 months i will be continuing to expand this code. The waypoints will be replaced by network of convex polygons. An AI can move anywhere inside these areas without concern of collision with any static geometry. Possibly a similar technique could be used for terrain ignoring slope changes under 80 degrees, but for our project terrain isn't needed.
@Tim and Michael - Thanks.
#6
"1) AI Pack - still in progress, although obviously my time is pretty much devoted to AA right now, Justin will no doubt announce the bigger picture plan for the pack in due course. Its not dead, hell, its not even pining for the fjords! its alive and well and living in a CVS near you! :)"
While he doesn't give and dates, it's still alive. Thanks again.
Nick
04/13/2005 (12:32 am)
Thanks for the info Tom. Coincidently, today in Phil's plan he quoted this:"1) AI Pack - still in progress, although obviously my time is pretty much devoted to AA right now, Justin will no doubt announce the bigger picture plan for the pack in due course. Its not dead, hell, its not even pining for the fjords! its alive and well and living in a CVS near you! :)"
While he doesn't give and dates, it's still alive. Thanks again.
Nick
Torque 3D Owner Jacob