At the risk of appearing to be using this thread as my personal blog, I'm going to toss out a few more ideas I'm thinking about; both to codify them in my own mind and to put them out there where smarter people who already know about these things can say, "No; that's a terrible idea." (Though, I'm keeping in mind Arcana's admonition that paraphrases to, "If people only ever waited for perfect solutions, most of the time they end up doing nothing.") OTOH, if I'm turning into Joshex, then someone needs to slap me upside the head and say, "Hey! Wake up!"
The biggest problem I have with all of this is that I'm having to embrace the idea of Rover as a pseudo-game-client and I have zero experience with 3D environmental programming. Despite that, and despite the fact that anything I do currently is likely to be rendered obsolete the first day that Codewalker posts, "Hey, I've added NPC's and LUA scripting to Paragon Chat!", I seem to still be stuck with a desire to see Rover "run away" in a "life-like" fashion instead of in a "train on rails" fashion.
So, I have two semi-related problems to solve: One is pathfinding, and the other is terrain navigation.
"Semi-related" because you can't begin to understand where the paths are without first understanding where the terrain is. This is the bit that I've been having trouble wrapping my head around. Scene graphs, I get, mostly. Collision math, I get, mostly. Determining how you decide what things to test for collision without having to test EVERYTHING, every clock tick, is the bit that's been eluding me.
The first step was to read a geobin file. I've got a parser that can do that now, even though I haven't put it to use yet. As an exercise of sorts, I DID make a clientmessages parser and generate a strings.cfg file from it. I can now modify all the strings in my personal Paragon Chat instance. Whee! I also learned, for instance, that the game client pre-generated instance names for every city zone up to around fifty instances, which is interesting, if not immediately useful. (Though it did make me wonder if I could ADD strings to strings.cfg that don't exist in clientmessages. I'm not sure what Paragon Chat would do with that. Probably just ignore it as a presumed typo.)
The point being that if I could use my Kaitai-generated parser to load up the whole clientmessages file without running out of memory, access the "P-strings" array and use that info to access the associated strings in the strings array, and write the whole thing out as a strings.cfg file then I should, in principle, be able to do the same process with the geobin parser. That is, I assume at this point that the parsers I'm generating out of Kaiti (I made a .bounds parser as well) will work as expected with minor touchups to insure that text decoding happens correctly. (Python gets touchy about insisting that things conform to your current code page if you're working in a Windows environment.)
Scene Graph
So, now I can theoretically read a zone map geobin, which is basically a serialized scene graph. So, the question is, "How do you deserialize it?"
Based on the output of bindump, it looks a lot like the original scene graph is being traversed and written out "leaves-first". The Refs array represents the first-level children of the scene Root. I'm not really sure why TextParser felt the need to write the "eldest" children seperately from the others, but there you go.
In any case - the first Defs encountered in the geobin file are the outer "leaves" of the grp_Atmosphere_NPC "branch", which is the first entry in the Refs array. Each group represents its own "branch" that can contain many child groups. The children refer back to their parent, and the parents eventually lead back to one of the root Refs. A parent group can contain multiple instances of a single child group. Defnames that contain file paths lead into the object library, where the geometry lives along with bin files describing each individual model in the .geo file as well as groups of models, and bounds data for the models, represented as both rectangular and spherical bounds.
Once all of the grp_Atmosphere_NPC nodes are read, the next node is a grand-child of Ref grp_audio, which is the next Ref in the Refs array. It appears safe to expect each of the following Refs to be "untraversed" in turn in order to completely deserialize the data in the bin file and arrive at something that resembles the original scene graph.
The issue of geometry rears its head at this point, since the ultimate termination of any particular path through the scene graph should be a piece of geometry that can be drawn or manipulated. Here is where I intend to cheat, using the advice Codewalker recommended last year - My bot can't actually "see" the world and it never intends to render anything visually. The contents of the actual .geo file is irrelevant. All that the bot cares about is the collision bounds. Which means that as far as the bot is concerned, it is living in either Boxville or Spheretown. Either way, the "geometry" of the zone is faked at this point using the data from the .bounds file for the individual objects in the zone. As far as I can tell, EVERYTHING is an object of some sort. Even the streets and sidewalks and plazas are all objects with a bounding box defined as well as the radius of a sphere that presumably likewise encompasses the object.
In short - there is no "ground", as such. Rather, the "ground" is whatever "object" an entities feet happen to be colliding with due to gravity. (I haven't actually followed this line of logic through for a forested/outdoor zone like Croatoa, though I EXPECT it to apply the same way.)
I should emphasize at this point that my tossing around terms like "scene graph" is not some indication that I'm at some high level understanding of the term. When it comes to most of this 3D visualization and rendering stuff, I can say that I'm past the level where the terms represent some sort of mystical incantation that causes pretty pictures to appear on a computer screen. Beyond that, I'm still pretty much Harry Potter in his first year at Hogwarts, and I'm definitely no Hermione.
So, now the question is: What do I do with this scene graph?
For starters, if Rover is going to be acting like a pseudo-client anyway then I figure I should use software suited to the task. That means loading up Openscenegraph and using it to manage the de-serialized scene graph for me. The minimal benefits are that I'll be using software designed for the task I'm trying to accomplish and if I want to actually visualize Boxtown or Sphereville for some reason, it should be possible to come up with some coding examples that illustrate how to do that.
It isn't entirely clear to me yet just how much collision detection is available in Openscenegraph (OSG, hereafter). There are different versions and the documentation ranges from recent to over a decade old. I THINK that I might be able to insert Rover's position and bounding box into the scene graph, and have it automagically incorporated into the scene, such that casting a ray in any given direction will return a list of objects that are potentially things Rover would collide with.
If that doesn't work, I've also found a fallback - Open Dynamic Engine (hereafter, ODE). This is more or less a physics engine sort of like Phys X but intended for doing rigid body simulations, with the "dynamic motion" component separated from the "collision detection" component, so you can use either of them standalone. Plus, ODE has a reasonably simple and easy-to-understand idea of the World and of Spaces. I THINK it would be relatively simple to load Boxville into a ODE World instance and have it treat all of the boxes as motionless/massless bits of terrain and then ODE can, given the position of Rover, deliver a list of collision points that he's likely to hit at his current position and velocity.
Either of these solutions results in Rover sort of "feeling" his way around the geometry of the world, without actually knowing the precise geometry of the world. Practically speaking, I think it would work like I mentioned back when I first brought this up last year, where I'd use the collision points to create an avoidance force that "repelled" Rover away from the obstacle but hopefully still in the general direction he "wants" to go in.
Pathfinding
The other benefit of the fully realized scene graph is that I've got the list of beacons and spawn points that I've mentioned several times previously. These are suitable for use as path waypoints, since each of them is guaranteed to be at "ground level" (with a few exceptions, like the blimp's path around Atlas Park). However - Waypoints without any paths between them aren't really useful.
The solution, as I see it, is to build a "neural net" graph that connects every waypoint with every other waypoint. I then feed that graph into a scanner whose job is to brute-force test each of the resulting line segments for collisions using the scene graph/terrain visualization. Segments that come up with a positive hit are dropped from the database. POSSIBLY, the scanner could check the height of the bounding box for the offending object and if it was shorter than some arbitrary jump height, that segment could be broken into two new segments that both terminate at the object and that both are marked as "jump over" at the endpoints near the obstacle. I think that would fall into "stretch goal" territory.
The end result would be a database of waypoints that each connect to at least one other waypoint, forming a graph of the "walkable" space in the zone. Such a graph could then be searched with a A* search or some similar pathfinding algorithm to dynamically find a path from any "point A" to any "point B" that lies within the graph. Such a database could be generated once and then used by any bot, even if that bot knows nothing at all about the geometry of the zone. As long as it was located somewhere on the "pathnet", it could find a way to every other part of it.
I'm only just at the barely beginning stages of realizing any of the above vision, but I believe that the above actually represents an achievable "spec" for a bot that can wander freely around any zone map or mission map in the game, given appropriate preparation.