Quote:
|
Originally Posted by Raddiux
perhaps some kind of script can be run after all the nodes are placed to spit out a grid file which has pre-calculated distances and LOS checks to nodes throughout the zone
|
That is the general idea. You do not need a LOS check, though, because a "connected" node implies that it is visible.
Quote:
|
Originally Posted by Raddiux
2.) How would the path-finding algorithm work once the nodes are in place? I still can't figure out how to handle Example C which I listed above. Any of you guys have any ideas?
|
Once connections between nodes are worked out, it is the travelling salesman problem. To find the shortest distance between two nodes, the solution can be intensive. AFAIK nobody has come up to a better solution yet. However, there may be other ways to help alleviate this problem, ie: a grid overlay on the zone, each node belonging to a section of the grid, and finding sub-paths.
This is how the graph would look for your
example C. All lines are bi-directional. I added node Z in place of your mob. The mob and player nodes are not REAL nodes, but instead each have a link to the node that they are "at."
The hardest part would seem to be finding a way to provide for auto node connection. For instance, if I have logged nodes A, B, and C, all visible, but only want travel possible from A<-->B<-->C, how do I accomplish this if I do not manually set connections? Labelling nodes may help with this (and labels could be thrown out after graph construction), but there may be better ways.