A* and atlas2
by Kirk Longendyke · in Torque Game Engine Advanced · 04/07/2007 (2:16 am) · 6 replies
First up, please bear in mind this is one of those notions that wakes you in the middile of the night and you just have to write it on down before you loose track of it. Since were talking somethin that could be useful to alot of different aplications, I'm choosing to write the storm on down here for folks to mull on over... (read here, it's 90% of a notion at best, so if you dislike dirty thinking, skip this one)
Now most folks that have dealt with ai are at least passingly familiar with pathfinding in one form or another, and are familiar with the a* algorythm. At it's core concept, it's about a network of interconnected points used to find your way from point origin[x][y] to point destination[x][y] via for lack of a better notion atm, well call it links[n][x][y]. It's the bit about the interconnected points that hit me like a brick a second ago...
Theres already quite a few rescources out there dealing with a*, in fact, so a baseline shouldn't be too hard to gather from them. You lay out a point-grid for where you can go, and you search-algy checks the links from origin to destination to see what the closest way to get there would be...
If (and I suppose thats a pretty big *if* when you get right down to it) chunk-lod works as I think she does to a degree, the heightmapping data already embedded in the thing could in fact serve a similar useage, going from one terrian deformation point to the next terrain deformation point (it is a series of points, yes? or am I totally misunderstanding the baseline structure for atlas storage here?)
As an aside, I've worked with 2 naving systems by way of the bf series games: the first, a simple 0/1 system from 1942 resembled nothign so much as a binary map for bots to traverse. the second, and this is what really has me thinking of possibilities here, is a navmeshig system that takes the terrain, and statics and (after a day or two) generates a 3-d model navMesh of where everything can go...
Basicly the notion would be rather than adding the overhead of a grided system, or additional navmesh, re-use the existing data by way of... the heightmap and a relatively simplistic findclosestvert function to get your bearings as it were so that we can avoid unnecessary memorry allocation altogeather...
Dunno how feasable this would possibly be, or if theres any particular 'gotchas' inherent in the idea, but since works still being done on the fomat anyway, figured i'd toss the notion on out, see what folks think... fraid at this point (aside from not even being sure if i'm coherent at 4am) for this to go much further is gonna require quite a bit of diging, so i guess a few questions are in order:
1- Is there a cleaner way that'll reduce the memory footprint *significantly*
2- how much hacking up the atlas2 file format this'd take
3- well, there was a 3, but can't remmeber right now. sure folks'll come up with a 3rd, 4th and 50th at some point. At minimum should be interesting to see what this post starts, eh?
Now most folks that have dealt with ai are at least passingly familiar with pathfinding in one form or another, and are familiar with the a* algorythm. At it's core concept, it's about a network of interconnected points used to find your way from point origin[x][y] to point destination[x][y] via for lack of a better notion atm, well call it links[n][x][y]. It's the bit about the interconnected points that hit me like a brick a second ago...
Theres already quite a few rescources out there dealing with a*, in fact, so a baseline shouldn't be too hard to gather from them. You lay out a point-grid for where you can go, and you search-algy checks the links from origin to destination to see what the closest way to get there would be...
If (and I suppose thats a pretty big *if* when you get right down to it) chunk-lod works as I think she does to a degree, the heightmapping data already embedded in the thing could in fact serve a similar useage, going from one terrian deformation point to the next terrain deformation point (it is a series of points, yes? or am I totally misunderstanding the baseline structure for atlas storage here?)
As an aside, I've worked with 2 naving systems by way of the bf series games: the first, a simple 0/1 system from 1942 resembled nothign so much as a binary map for bots to traverse. the second, and this is what really has me thinking of possibilities here, is a navmeshig system that takes the terrain, and statics and (after a day or two) generates a 3-d model navMesh of where everything can go...
Basicly the notion would be rather than adding the overhead of a grided system, or additional navmesh, re-use the existing data by way of... the heightmap and a relatively simplistic findclosestvert function to get your bearings as it were so that we can avoid unnecessary memorry allocation altogeather...
Dunno how feasable this would possibly be, or if theres any particular 'gotchas' inherent in the idea, but since works still being done on the fomat anyway, figured i'd toss the notion on out, see what folks think... fraid at this point (aside from not even being sure if i'm coherent at 4am) for this to go much further is gonna require quite a bit of diging, so i guess a few questions are in order:
1- Is there a cleaner way that'll reduce the memory footprint *significantly*
2- how much hacking up the atlas2 file format this'd take
3- well, there was a 3, but can't remmeber right now. sure folks'll come up with a 3rd, 4th and 50th at some point. At minimum should be interesting to see what this post starts, eh?
#2
http://img57.imageshack.us/my.php?image=picaa6.jpg
might help a bit with the visualiation
04/08/2007 (12:43 pm)
Actually, the irregularities of the linked list of pointers inherent in the implementation was half the point, since a* uses a (typicly) least nodes passed through function to decide which direction to go along the potential paths from point a to point b. Still trying to get my thoughts in order on this one a bit. was also why I put a getclosestvert query on the list of 'would have to do's', if that makes any sense. Hate to be so unscienific about it as to admit that i'm still *feeling* my way through the notion, but... yeah... should have also mentioned how rasterisers work a bit i guess, come to think on it, considering the more artistic bent of most... what *they* do, when drawing a line, is to turn on the closest pixel on/off (ok, so the apropriate 4 bits, but thats waaaaaaaaaaaaaay beyond scope). http://img57.imageshack.us/my.php?image=picaa6.jpg
might help a bit with the visualiation
#3
IMHO I would stay away from the Atlas file(s) simply because there are much easier way to do this.
First, I think that you would need a map of the terrain.
1) You can use the heightmap that the Atlas terrain was build from, just don't go to the Atlas file to get it.
2) Or you could use a map of your own making. This sounds to me like the best route, because your can record much more information in your own map then can be stored in a simple heightmap. Of course you would need to build a tool to create your map. I am imagining a 24 bit RGB image, you would have two bytes to store the 16 bit of height information. Plus 8 more bits flags for things not obvious in the heightmap, like minefield, impassible vegitation, water, etc. You probably want the map image to be the same size and therefore the same resolution as the heightmap.
Now to get the heightmap or image map into the game you could
Add another field to the AtlasInstance2 object with a path to the heightmap or map.
new AtlasInstance2(YourTerrain) {
canSaveDynamicFields = "1";
position = "0 0 0";
rotation = "1 0 0 0";
scale = "1 1 1";
detailTex = "~/data/terrains/details/detail1";
atlasFile = "~/data/terrains/terrain1.atlas";
mapFile = "~/data/terrains/maps/terrain1.map";
or
HFFile = "~/data/terrains/terrain1.raw";
lightMapSize = "1024";
};
I have not dealt with AI in TGEA. There maybe easier ways to do this in the AI system. This is just how I would approach the problem just off the top of my head.
04/13/2007 (5:37 pm)
Kirk,IMHO I would stay away from the Atlas file(s) simply because there are much easier way to do this.
First, I think that you would need a map of the terrain.
1) You can use the heightmap that the Atlas terrain was build from, just don't go to the Atlas file to get it.
2) Or you could use a map of your own making. This sounds to me like the best route, because your can record much more information in your own map then can be stored in a simple heightmap. Of course you would need to build a tool to create your map. I am imagining a 24 bit RGB image, you would have two bytes to store the 16 bit of height information. Plus 8 more bits flags for things not obvious in the heightmap, like minefield, impassible vegitation, water, etc. You probably want the map image to be the same size and therefore the same resolution as the heightmap.
Now to get the heightmap or image map into the game you could
Add another field to the AtlasInstance2 object with a path to the heightmap or map.
new AtlasInstance2(YourTerrain) {
canSaveDynamicFields = "1";
position = "0 0 0";
rotation = "1 0 0 0";
scale = "1 1 1";
detailTex = "~/data/terrains/details/detail1";
atlasFile = "~/data/terrains/terrain1.atlas";
mapFile = "~/data/terrains/maps/terrain1.map";
or
HFFile = "~/data/terrains/terrain1.raw";
lightMapSize = "1024";
};
I have not dealt with AI in TGEA. There maybe easier ways to do this in the AI system. This is just how I would approach the problem just off the top of my head.
#4
I think Mary is absolutely right. Stay away from the atlas mesh itself, as it really isnt useful for navigation purposes, although you CAN generate a mesh using data present in the atlas mesh.
What I mean is, you would NOT use the vertices of the atlas mesh, because at different levels of detail those are decimated and actually, convey less of the useful information that you need anyway.
What you really need, is for exteriors at least, "volume of potential movement" meshes. That is, meshes within which you can safely move without collision. Typically, I've used waypoint graphs, where you generate nodes and you generate node adjacency information that says wether a particular waypoint is visible from another. I now think that this method is unsatisfactory for a number of reasons.
I've been planning a system based of a Prof Mark Overmars presentation I saw a year and a half ago, which involved using waypoint graphs to generate an actual volume based mesh representation. I wont go into detail, but hopefully I'll be pushing this either as a paper for my PhD or as a project for my masters students.
At the end of the day, I'd advise you to go the common route of waypoint graph generation initially. It works for the most part, you can deal with the failure conditions, plus it would work under any terrain implementation.
04/14/2007 (12:13 pm)
I'll chip in, as I've done several different systems and seen others work in this area.I think Mary is absolutely right. Stay away from the atlas mesh itself, as it really isnt useful for navigation purposes, although you CAN generate a mesh using data present in the atlas mesh.
What I mean is, you would NOT use the vertices of the atlas mesh, because at different levels of detail those are decimated and actually, convey less of the useful information that you need anyway.
What you really need, is for exteriors at least, "volume of potential movement" meshes. That is, meshes within which you can safely move without collision. Typically, I've used waypoint graphs, where you generate nodes and you generate node adjacency information that says wether a particular waypoint is visible from another. I now think that this method is unsatisfactory for a number of reasons.
I've been planning a system based of a Prof Mark Overmars presentation I saw a year and a half ago, which involved using waypoint graphs to generate an actual volume based mesh representation. I wont go into detail, but hopefully I'll be pushing this either as a paper for my PhD or as a project for my masters students.
At the end of the day, I'd advise you to go the common route of waypoint graph generation initially. It works for the most part, you can deal with the failure conditions, plus it would work under any terrain implementation.
#5
04/14/2007 (2:16 pm)
Thanks for the feedback. All in all, saved a bit of time and headache I suppose, though I can't help but think large-ish webs for pathfinding in addition to the ones already inherent in the atlas set is going to cause some greif down the road...
#6
Another question at hand is whether it would be good to build the representation off of some level of the atlas mesh or off of something else.
It's really important to have your solution fit the problem. When pathfinding over a relatively flat outdoor terrain, often a straight line is a viable path. This is obviously not the case for even a mildly complicated map, especially one with pockets that a unit could get trapped in. If you implement waypoints, however, I would expect pathfinding to be pretty robust. You could allow units to wander off of the paths to chase and in the process you would be able to implement a lot of behavior with very little work. I like the idea of using the heightmap, but that's only the very beginning of whatever you would need to do.
05/14/2007 (9:35 pm)
Kirk I've done a similar thing to what you are talking about but I did it with Interiors. What I found was that .dif files don't have a huge number of flat, walkable polygons so it created a pretty small search space. Even still, I create an abstract representation of the nodes for actual pathfinding. No matter what, you will need some sort of extra data to facilitate pathfinding, the overhead in memory will be worth it in performance.Another question at hand is whether it would be good to build the representation off of some level of the atlas mesh or off of something else.
It's really important to have your solution fit the problem. When pathfinding over a relatively flat outdoor terrain, often a straight line is a viable path. This is obviously not the case for even a mildly complicated map, especially one with pockets that a unit could get trapped in. If you implement waypoints, however, I would expect pathfinding to be pretty robust. You could allow units to wander off of the paths to chase and in the process you would be able to implement a lot of behavior with very little work. I like the idea of using the heightmap, but that's only the very beginning of whatever you would need to do.
Torque Owner Dennis Trevillyan
WatreGames
Anything done using the existing atlas terrain mesh will be very coarse.