@MuddyMole thank you for the link and example, I'll take a look!
@Yves I've always supposed hidden lists worked like an array internally cause it can be pretty fast, if it's not, I'll all in favor of adding the option so it can performs even better!
I know the scrollbar makes it slower, being visible even more...
I had a thought...
The idea is to separate the vertices used to define walls for line-of-sight tests, from nodes used in pathfinding (right now, they're the same thing). We can do this by automatically creating a second polygon inside the first.
Anything inside the pink or blue areas is considered out of bounds (unclickable).
The blue lines are used in line-of-sight tests.
The purple nodes are used in pathfinding (in fact, as an added bonus, we can remove any concave nodes, such as #5 in the image above, since a path will never pass through them).
Yeah, I think this is the correct way to fix your last exemple!!! Is not a real navigation mesh but for point and click game and similar this is a really great pathfinding
I haven't tested, tidied or commented it properly yet, but if anyone wants to try out the latest version of my polygon-based pathfinding example, it's here:
https://1drv.ms/u/s!Atq7cUIJ7uextBrL...k_zuw?e=dmgbna
(let me know if you find any bugs, please)
A few basic usage notes:
- each polygon is defined as a list of numbered nodes in the hidden list object
- they MUST be listed in clockwise order
- node ids MUST be 2 digits long (eg. "05" not "5")
- Fusion numbers nodes in the order they were created (they will be labelled at runtime)
- do NOT repeat the first node at the end (unlike the previous version)
You are the best my friend! I'll take a fast look now, and it's amazing!
In these days I will test it better and let you know as soon as I can if I find some bugs
Thanks again for your fantastic work!!!
Awesome update, MuddyMole!
Whenever I got some spare time I would like to try making a system that automatically triangulates a level, specially considering moving obstacles!
My example does a ton of calculations at the start of the frame, in order to minimize the amount needed during the actual pathfinding process. It probably wouldn't be hard to just create an "updateMap" function, but I don't know what effect that would have on performance.
Automatically generating the nodes is an interesting problem, but it would be handy. I had a few thoughts about that, as the current system is quite clunky.
1.) Create a custom map editor or other tools - the best option by far, but more work.
2.) Use prefabricated obstacle objects. These would be actives, and would have one frame of animation for each of their nodes, with the position of the action point determining the node's position. At the start of the frame, create the nodes and paste the active into the background.
3.) Use tile-based maps. It might seem like an odd idea, since there are already other pathfinding extensions/examples that work on grids, but this has the potential to be far more efficient, as it can drastically reduce the number of nodes required, and plus it's pixel-perfect and gives 360 degree movement. It would be easy to use the usual auto-tiling technique to identify corner tiles and create nodes at their position.
My example does a ton of calculations at the start of the frame, in order to minimize the amount needed during the actual pathfinding process. It probably wouldn't be hard to just create an "updateMap" function, but I don't know what effect that would have on performance.
Automatically generating the nodes is an interesting problem, but it would be handy. I had a few thoughts about that, as the current system is quite clunky.
1.) Create a custom map editor or other tools - the best option by far, but more work.
2.) Use prefabricated obstacle objects. These would be actives, and would have one frame of animation for each of their nodes, with the position of the action point determining the node's position. At the start of the frame, create the nodes and paste the active into the background.
3.) Use tile-based maps. It might seem like an odd idea, since there are already other pathfinding extensions/examples that work on grids, but this has the potential to be far more efficient, as it can drastically reduce the number of nodes required, and plus it's pixel-perfect and gives 360 degree movement. It would be easy to use the usual auto-tiling technique to identify corner tiles and create nodes at their position.
In the last few days I have been testing your example and I must say it works great! Even on android (I removed the surface object) it works great. For my type of game this example is the best and I honestly have no idea what could be improved because it is super fast and bug free.
The only request would be to reimplement the contour lines of the generated polygons without the surface object, but just for debugging, for my game this example is just perfect, and I particularly want to thank you once again for your fantastic work!
Posting Permissions
Reply With Quote
