That looks to me still to be an A* algorithm. Eliminate tiles which are blocked (simply by recording that the tile is obstructed in this map), and use local steering to avoid obstacles. If it is possible that local steering makes no sense (e.g a tile may only be occupied by a single entity), then you can avoid steering and consider a tile blocked if it has > 0 entities (wall / npc) within it.
If many agents are going to use pathfinding, it might make sense to refresh this state before performing A* so that the search doesn’t take longer, e.g by having the NPCs check their tiles, and if they’ve changed since last frame, exit the previous tile, and enter the new one (modifying each tiles’ entity count)
I’d agree that the built in navmesh is not an appropriate tool for this game, given its dynamic nature.
Find all xy*size grid position z (height) values of the plane.
Collect the (gridX,gridY, z ) tuples in a set.
Raycast from (gridX,gridY, z+e ) to (gridX,gridY, z )
[LIST]
edit: “e” being the height that has to be clear
If hitObject and slope<0.9 : spawn “Node” (visulizer)
[/LIST]
This takes less than sec…
It searches all of the mesh, so even disconnected pieces (like the floater) are graphed.
As I use a unit grid, there is no need to precalculate all the valid connections.
That means that during A* a node can just ask if there is any node to its left (plus-minus n amount of unit height).
( graph.get( (thisPos+vectorLeft+vectorDeltaH).to_tuple(0), None) )
How I would imagine this A* to work:
Each blocking object knows its volume in the unit grid
[LIST]
for example the cuboid of min & max axis values of the mesh vertices
Each blocking object updates the nodes that are in its volume or have left its volume.
Each path following actor checks the nodes in its path if they change values ( to being blocked ).
repath if needed
Each node contains a data object(dict?) to match the path ticket ( ID ) and node cost( G,H and F)
This way No cleaning or refreshing the whole graph would be needed
Each time a node is visited old tickets are discarded.
I usually do my pathfinding myself by using placed nodes. If you place a node in even intervals, then you kind of end up with an A* pathfinding map setup, and if you place nodes only at places of importance, then you get something that should be smoother and easier on the CPU.
In any case, my implementation added in weights so that you could specify which routes were impossible (no link between two nodes), which were preferred (path between a target and starting node with a low overall cost), and which were secondary / less like-able (path between a target and starting node with a high overall cost). If you have something like a locked door, then you can just delete the link between nodes on each side of the node and recalculate the path. Or, raise the cost of the link between both sides so an alternative (breaking down the door) is possible, but not advisable unless there is no other way.
If you want to have something where an NPC is less likely to take a certain route to avoid walking toward an NPC, then you could make it so that any NPC raises the cost of the nodes it’s near, making other NPCs choose other nodes to walk on when pathfinding unless it’s necessary.
If you want objects not to pass through each other, then as some guesses, you can:
Run pathfinding often (say, after each successful step) to create paths around moving objects.
Flag certain points to be “off-limits” to all other paths while the objects on paths using those points are in motion. So, for example, directing the player to move to a point will make that point and/or surrounding points off-limits, which means that other objects can’t navigate through that zone.
Detect when objects are unable to finish their paths and stop them, Sims-style.
Also, move objects to the furthest point on the map that they can move to unimpeded. That would help different NPCs to take different routes.
Anyway, it should be possible to do effectively for an A* algorithm, it seems. I’d imagine you’re going to use this for that overhead RPG game you were working on, right?
Getting to your previous questions:
Why can’t you use pathfinding with randomly generated levels?
Nah, not really - I think I’d lose interest if an already turn-based game took seconds to switch turns, and especially so if it were regular and predictable (i.e. every enemy turn with a low number of NPCs on the game field).
It’s a bit of a mess still since it’s still a WIP, but I think you can see where it’s going.
@@VegetableJuiceF
I don’t think it really needs such a dense graph, you can use path smoothing with raycasting to make a chunky graph look smooth.
Also, when generating a graph, you could make it regularly spaced but then you are quite restriced when it comes to designing your tilesets. Either you use a very dense grid with high overhead or you use a loose grid and risk some nodes being badly spaced (for example no node in a doorway would make it difficult to get through). With using a mesh you can have irregular nodes and use the mesh data to see which nodes should be connected, i.e. check which ones share verticies (or vertex positions, since I need for meshes to be separate for tile placement) you can also vary the density of the graph, with more nodes around areas which need them, such as tables or crates or doors or traps.
I’m sure I can speed up the harvesting of data from the meshes, but I’d like to have quite big levels, so eventually it’s going to get to a point where even an optimal script is going to take time to execute.
@@SolarLune I usually use nodes too for outside maps but here the mesh is serving a double purpose in that it is acting as the point and click interface. You have to click on the mesh (which is slightly smaller than the room) to move somewhere. I’ve gone back and forth in my thinking about that, since another great thing about nodes is you can add extra ones, for example when you spawn a table, you can also spawn some extra nodes around the table and add them to your graph for extra density where it is needed. Still, I guess it wouldn’t be hard to mix a mesh based graph and a node based graph…
Anyway, talking it out on the forum always gives me great ideas, or reminds me of things I was going to do but forgot about.
Well a (fast) map with no additional calculation is better in my oppinion.
Being enough dense by having no blocking object smaller than the resolution is enough.
pre optimization is the root of all evil
The overhead wasn’t a problem.
The complexity is something like (mapSize/graphResulution)**2.
Like, the only calculation needed was the initial 1 seccond.
Paths between rooms can also be reused, making long distance pathing more viable.
What is the complexity of yours? Finding all nodes, then checking all connections…
And depending on skills, are you sure you can optimize your graph better than a dense graph? Make one mistake, and being on the table could make you invisible.
You should be using a navigation mesh in modern games, they yield much more sensible paths and contain more information about the world than just a node based graph. Increasing graph resolution is hammering a nail with a screwdriver.
You can find the A* path (or other algorithms) between polygon midpoints, and then use a simple local navigation system to move through that path. I’ve an example here of using the funnel algorithm to find the shortest path through the navigation mesh. Realistically, you should use local navigation methods to follow this path (and can implement collision avoidance with this), which is what I’m currently working on
