Last night, I finished the recursive algorithm that generates the next hop information for each Free Move Zone (FMZ), destination, and portal. It loads an Autodesk fbx environment using the content processor, and, based on some mesh naming conventions, it automatically generates the FMZs and portals within XNA. I had been fighting with simple issues--like accidentally resetting the center point of my portals--but now it is good to go. Here's the reasoning behind next hop forwarding:
- Each FMZ (f) has a set of portals (p) that lead to other FMZ's
- I go through every other FMZ (g) and I use A* to find the shortest path to each zone in g after going through each of the portals in p.
- If you cannot navigate to a zone from a portal in p, it is assigned a distance of -1, and otherwise, it is assigned the distance that is measured between portals until you reach the zone (adjacent zones in f and g have distance 0 because they share a portal).
- Using this information, I can determine the fastest route to a point within a destination FMZ given a point that is within the starting FMZ.
Later today--to make doubly sure I don't get behind--I'll be making some simple NPCs navigate between areas--to start off, they will only move in straight lines between portals to reach the center point of some zone or another.
I'll post some code samples for both topics after I make sure the NPCs navigate well.
Signing off,
Jason
No comments:
Post a Comment