It's the pathgrid in the original Morrowind, actually, that I don't like. It's the old pathfinding technique with simple waypoint graphs, instead of navmeshes. This is actually the reason why pathfinding tends to fail in the original game.
Navmeshes will really help us get better pathfinding that behaves more like in modern games, as characters will be able to plan a path in the full space of the floor, instead of only over a few predefined paths. This would allow them to avoid more obstacles, be less prone to getting stuck, etc.
It could still be useful to investigate if we can use those graphs in some way, in combination with navmeshes. For example for auto traveling on the map.
Interested in participating
Re: Interested in participating
The pathgrid is a piece of junk that can't cross cell boundaries by design. You are better off moving to a navmesh. The big deal with Morrowind is handling interacting mod changes, I hope you can get that working.
Re: Interested in participating
That's one of the reasons why I'd be interested in researching dynamic navmesh generation (at runtime or loadtime) to solve this problem.Hrnchamd wrote:The big deal with Morrowind is handling interacting mod changes, I hope you can get that working.
Of course there is the issue of how to generate the high-level travel graphs that needs serious consideration.
The alternative is to allow building and editing the navigation structures in the editor. We would probably need some kind of incremental data format for adding modifications to the navigation data in a hotpluggable manner.
Interesting read: http://digestingduck.blogspot.be/2010/0 ... nding.html
This could be one way of doing it.
Re: Interested in participating
You could generate a navmesh out of the existing hand generated pathgrid, thus still keeping with the desired travel areas for npcs in town but removing the stuck to rails appearance and inability to avoid obstacles.
Re: Interested in participating
That's an option. Another option is letting recast rasterize the entire area on its own, then using the existing pathgrids to floodfill the navmesh and prune any disconnected polygons.
Re: Interested in participating
Don't see a reason to use pathgrids with navmeshes in any way except for patrol waypoints.
Re: Interested in participating
Please keep in mind that we need to keep compatibility with vanilla MW. While I agree that the current path grid is a suboptimal solution, ignoring it completely might break some plugins that rely on certain routes. Post 1.0 we probably should add a GMST flag for ignoring the old path grid, but for now we need to respect it in locations where it exists.
I am somewhat skeptical about creating additional pathing structures at load/run time. Sounds slow. From my experience these kind of things are best done in the editor. We need to extend the ESX format anyway post 1.0, so it is not a problem to add additional record types.
I am somewhat skeptical about creating additional pathing structures at load/run time. Sounds slow. From my experience these kind of things are best done in the editor. We need to extend the ESX format anyway post 1.0, so it is not a problem to add additional record types.
Re: Interested in participating
Perhaps it would be best to use navmeshes for cells that have them, falling back to the path-grids if not. As much as I'd like navmeshes for path-finding, I'm not sure if using an automated build of them would be that good (thinking dynamic map changes that could block or expose routes; and if it's anything like the navmesh builder in Skyrim's CK, it isn't perfect and needs some fixing up by hand).Zini wrote:Please keep in mind that we need to keep compatibility with vanilla MW. While I agree that the current path grid is a suboptimal solution, ignoring it completely might break some plugins that rely on certain routes. Post 1.0 we probably should add a GMST flag for ignoring the old path grid, but for now we need to respect it in locations where it exists.
In that case, enabling navmesh path-finding is just a matter of providing a plugin with navmesh cell data.
Re: Interested in participating
I understand that it's important not to break any existing content.
(Linear) waypoint structures are often still a part of navigation with navmeshes. While you could let it calculate a path from begin to end point, more control can be obtained by introducing a linear set of waypoints that the character has to follow. This will require a character to pass at a certain minimal distance of the waypoint before it can go to the next.
Waypoints remain, but their purpose changes. Instead of being the data used for pathfinding, they become more high-level sub-goals of the AI. The navmesh navigation library will handle the low-level AI task of pathfinding.
I would have to test this in actual MW scenarios, but it's possible that the points in the waypoint graph can be converted to waypoints that can be used on top of a navmesh.
The idea is that agents are free to choose any path they deem appropriate to reach the next waypoint, making them much more free to use all available space to avoid obstacles and reach their destination. On the other hand, you can gain a lot of control over the actual route that characters will follow by placing waypoints close to each other. Since agents will always search for shortest paths, there is a very high chance they will move directly towards their destination in a straight line or smoothed curve.
Regarding dynamic level changes: recast is quite powerful and can handle dynamic changes to the navmesh in realtime. It's possible to block paths or add new objects on which can be navigated.
It's been used in actual games for this purpose.
(Linear) waypoint structures are often still a part of navigation with navmeshes. While you could let it calculate a path from begin to end point, more control can be obtained by introducing a linear set of waypoints that the character has to follow. This will require a character to pass at a certain minimal distance of the waypoint before it can go to the next.
Waypoints remain, but their purpose changes. Instead of being the data used for pathfinding, they become more high-level sub-goals of the AI. The navmesh navigation library will handle the low-level AI task of pathfinding.
I would have to test this in actual MW scenarios, but it's possible that the points in the waypoint graph can be converted to waypoints that can be used on top of a navmesh.
The idea is that agents are free to choose any path they deem appropriate to reach the next waypoint, making them much more free to use all available space to avoid obstacles and reach their destination. On the other hand, you can gain a lot of control over the actual route that characters will follow by placing waypoints close to each other. Since agents will always search for shortest paths, there is a very high chance they will move directly towards their destination in a straight line or smoothed curve.
Regarding dynamic level changes: recast is quite powerful and can handle dynamic changes to the navmesh in realtime. It's possible to block paths or add new objects on which can be navigated.
It's been used in actual games for this purpose.
Re: Interested in participating
Dear OpenMWersduststorm wrote:I understand that it's important not to break any existing content.
(Linear) waypoint structures are often still a part of navigation with navmeshes. While you could let it calculate a path from begin to end point, more control can be obtained by introducing a linear set of waypoints that the character has to follow. This will require a character to pass at a certain minimal distance of the waypoint before it can go to the next.
Waypoints remain, but their purpose changes. Instead of being the data used for pathfinding, they become more high-level sub-goals of the AI. The navmesh navigation library will handle the low-level AI task of pathfinding.
I would have to test this in actual MW scenarios, but it's possible that the points in the waypoint graph can be converted to waypoints that can be used on top of a navmesh.
The idea is that agents are free to choose any path they deem appropriate to reach the next waypoint, making them much more free to use all available space to avoid obstacles and reach their destination. On the other hand, you can gain a lot of control over the actual route that characters will follow by placing waypoints close to each other. Since agents will always search for shortest paths, there is a very high chance they will move directly towards their destination in a straight line or smoothed curve.
Regarding dynamic level changes: recast is quite powerful and can handle dynamic changes to the navmesh in realtime. It's possible to block paths or add new objects on which can be navigated.
It's been used in actual games for this purpose.
I'm writing here with the same idea: to express my interest in participating of AI implemetation. I was following previous months the OpenMW development and it was said that some functionality was already implemented. I really would like to know more about it, because I have certain notions of working with AI algorithms.
All information I could find on this matter is these pure lines of code: https://github.com/zinnschlag/openmw/tr ... wmechanics
Moreover, does Morrowind AI come to nothing more than pathfinding? I suppose it is also conducting battles and it might be tricky, no?
Best regards,
soshial