Plan for Josh "The_Force" Moore
by Josh Moore · 04/27/2005 (10:53 pm) · 11 comments
Me, Myself, and A*
I was originally inspired by this .plan to try my hand at A Star path finding in Illumina. However, after reading about the algorithm on various websites, I still had no idea how it works or how to implement it. A few weeks later, I stumbled upon this T2D A* tutorial. At this point, I already had a custom AIWayPoint class made, and had written the code to link each node withing LOS of each other(because I already tried some kind of path finding....).
So with the T2D tutorial as a guide, I went about getting A* to work in my game. I didn't totaly know what I was doing, but I had to try it never-the-less. When I thought it all was in place and should work, I booted up Torque and spawned a bot. To my amazement, the bot walked out of my base, around the base walls, and went right into the garage in the back of it. I couldn't believe it worked!
Now I had nodes that were linked via script by LOS, but I had no way of telling which nodes were connected to which. I bugged eXoDuS on IRC for some help on rendering lines to each linked node, but all he gave me was "glBegin(GL_LINES)". A bit later I got it working on my own(yay for me :o). Once I got back in game and saw all the node connections, I knew I had todo something like eXoDuS did in his path finding work: give each node a "maxLinkLength" varible. That made it so nodes wouldn't get linked to each other if they were to far apart.
At this point, I had the node linking code complete and had a great way to debug the "node web" as I like to call it. But, the path finding wasn't quite working good enough. It turned out that all the bugs I encountered were just simple coding mistakes and bad node linking. I fixed all that, and now the bots can find a path from any node to any other node perfectly. It's damn fun(at least for me) to watch the bots running from node to node. It'll be really fun once I get actaul AI working, not just the path finding.
Here's some screenies of the "node web":
All this in about a day of actual work. Don't laugh, I'm still a noob. ;)
Illumina
Illumina is comming along nicely, and we've been making some really cool progress in this past month. Our artist, Chris "TribalMa5ter" White has been turning out some sweet stuff: animated .dts doors with proper collision, hacking terminals(these are also used to open the large base doors), and a brand new snow map: Frost Bitten. Dyanmic weather(thunder storms, dust storms, ect) and meteor showers were also recently added to Illumina.
Big news, for the Illumina team, is the merging of Single Cell and Star Cave Studios as seen here: www.garagegames.com/blogs/38111/7699
We're all glad to be partnered with Star Cave, and hope to get Illumina to be the best game it can be.
That's about it, I hope there's enough screenshots and links to make at least a few people read throught it....
I was originally inspired by this .plan to try my hand at A Star path finding in Illumina. However, after reading about the algorithm on various websites, I still had no idea how it works or how to implement it. A few weeks later, I stumbled upon this T2D A* tutorial. At this point, I already had a custom AIWayPoint class made, and had written the code to link each node withing LOS of each other(because I already tried some kind of path finding....).
So with the T2D tutorial as a guide, I went about getting A* to work in my game. I didn't totaly know what I was doing, but I had to try it never-the-less. When I thought it all was in place and should work, I booted up Torque and spawned a bot. To my amazement, the bot walked out of my base, around the base walls, and went right into the garage in the back of it. I couldn't believe it worked!
Now I had nodes that were linked via script by LOS, but I had no way of telling which nodes were connected to which. I bugged eXoDuS on IRC for some help on rendering lines to each linked node, but all he gave me was "glBegin(GL_LINES)". A bit later I got it working on my own(yay for me :o). Once I got back in game and saw all the node connections, I knew I had todo something like eXoDuS did in his path finding work: give each node a "maxLinkLength" varible. That made it so nodes wouldn't get linked to each other if they were to far apart.
At this point, I had the node linking code complete and had a great way to debug the "node web" as I like to call it. But, the path finding wasn't quite working good enough. It turned out that all the bugs I encountered were just simple coding mistakes and bad node linking. I fixed all that, and now the bots can find a path from any node to any other node perfectly. It's damn fun(at least for me) to watch the bots running from node to node. It'll be really fun once I get actaul AI working, not just the path finding.
Here's some screenies of the "node web":
All this in about a day of actual work. Don't laugh, I'm still a noob. ;)
Illumina
Illumina is comming along nicely, and we've been making some really cool progress in this past month. Our artist, Chris "TribalMa5ter" White has been turning out some sweet stuff: animated .dts doors with proper collision, hacking terminals(these are also used to open the large base doors), and a brand new snow map: Frost Bitten. Dyanmic weather(thunder storms, dust storms, ect) and meteor showers were also recently added to Illumina.
Big news, for the Illumina team, is the merging of Single Cell and Star Cave Studios as seen here: www.garagegames.com/blogs/38111/7699
We're all glad to be partnered with Star Cave, and hope to get Illumina to be the best game it can be.
That's about it, I hope there's enough screenshots and links to make at least a few people read throught it....
About the author
#2
04/28/2005 (3:35 am)
Andy: thats pretty much the navigation mesh concept. used in Quake3 and a few other games.
#3
04/28/2005 (5:40 am)
Maybe someone will post resource to A* PathFinding for TGE ? that will be great 
#4
04/28/2005 (6:19 am)
According the Josh - He is going to release it as a resource when it is finished.
#5
@Chris: I said I might release it as a resource, mainly because I'd want someone to improve upon it and share their code.
I used that T2D A* resource as an example; 3 days ago I had no idea how to do any kind of path finding. If I can do it, anyone can. :o
04/28/2005 (9:18 am)
@Andy: That sounds like a great idea for navigating on the terrain, but I believe it would be out of my skill range.@Chris: I said I might release it as a resource, mainly because I'd want someone to improve upon it and share their code.
I used that T2D A* resource as an example; 3 days ago I had no idea how to do any kind of path finding. If I can do it, anyone can. :o
#6
Phil: in my experience with the Quake 3 engine, all that stuff is under the hood, not accessible to the scripter/level builder. Everything that a scripter/level builder did was node based. What do you think of this hybrid approach?
04/28/2005 (10:11 am)
Nah, its not out of your skill range :) If you can do what you just did, you could do it the way I described it. I was just rambling, reminiscing. Possibly a little innebriated at the time. I'm not telling.Phil: in my experience with the Quake 3 engine, all that stuff is under the hood, not accessible to the scripter/level builder. Everything that a scripter/level builder did was node based. What do you think of this hybrid approach?
#7
04/28/2005 (11:03 am)
There does seem to be a problem with all these nodes: it's slowing the game down. ATM, I only have 63 node objects at one base, and that's not even enough for that base. Only about 10 of them on are the terrain. Ben G told me on IRC that all those object in the scene graph would slow things down, but that didn't seem like the case last night(and maybe it's not :-o). Perhaps if I made the AIWayPoints not shapeBases, it'd help a little bit.... 
#8
Also i've been told that Doom3 extended this concept into full 3d convex hulls. I suppose this is because of their flying enemies.
04/28/2005 (12:55 pm)
Andy and Phil: CounterStrike's official bot uses this method. See this powerpoint.Also i've been told that Doom3 extended this concept into full 3d convex hulls. I suppose this is because of their flying enemies.
#9
Update: I added a tolerance value to the nodes so you can set how close the bot needs to get to the node to call onReachDestination. So now bots don't look soo retarded when traversing terrain nodes. I've also begun work on the actual AI part of the code, very fun stuff. ;)
04/28/2005 (3:25 pm)
Well, I don't think all the nodes are slowing it down, it must of been my meteor showers.Update: I added a tolerance value to the nodes so you can set how close the bot needs to get to the node to call onReachDestination. So now bots don't look soo retarded when traversing terrain nodes. I've also begun work on the actual AI part of the code, very fun stuff. ;)
#10
GameBase is your friend. Heck, even SceneObject, you don't need any networking.
04/28/2005 (8:53 pm)
Man!!! you derived way points from shapebase!? Shame on you mate :)GameBase is your friend. Heck, even SceneObject, you don't need any networking.
#11
and some waypoint drawing code. It's about as low cost a primitive for waypoints that you can get and i can have thousands and perform fairly well.
04/28/2005 (9:28 pm)
In my AI pathfinding hack i skipped SceneObject and GameBase all together. I created a WaypointManager class that holds a Vector
Torque 3D Owner Andy Schatz
I've always been disappointed that no one ever used this scheme. I feel like its superior to the typical node based navigation scheme for 3d agents.
Anyways, your plan reminded me of that scheme. Illumina looks great! Congrats.