Pathfinding causes stopped frame

[applebus]

If you were to block out a box of unavailable path, with available path on the inside (but no route to the path), it causes a massive frame drop.

I.E.

You can replicate by clicking on a green node inside the square of red nodes. Any way to remove this drop?

[SnpM]

I think the problem here is that there is no viable path from outside to inside the boxes. The pathfinding algorithm searches every possible node to confirm that.

There isn't an easy solution that doesn't boggle down pathfinding in general. Gotta think on this one.

On Wednesday, January 31, 2018, applebus notifications@github.com wrote:

If you were to block out a box of unavailable path, with available path on the inside (but no route to the path), it causes a massive frame drop.

I.E.

[image: image] https://user-images.githubusercontent.com/1331490/35654266-57f597e8-06ba-11e8-86c3-992b6c67d1c5.png

You can replicate by clicking on a green node inside the square of red nodes. Any way to remove this drop?

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/SnpM/LockstepFramework/issues/137, or mute the thread https://github.com/notifications/unsubscribe-auth/AHXqpxRTRwy8t6tu4gGTFtDMBvJ3N7O4ks5tQQE0gaJpZM4R02uv .

[applebus]

Thanks. This would allow doors and other type of passage blockers.

[SnpM]

Ok I gave it some thought and here's an elegant solution I think will do the trick.

Raycast from destination to start on the grid. If the raycast hits an unwalkable node, it will trace along the "shoreline" of the unwalkable nodes, orbiting clockwise around the destination node. If it fails to find an unwalkable node in the clockwise direction, it will assume that the wall is broken and that the destination node isn't trapped. If the trace loops back to the original node, a closed path is detected.

Due to the selective direction of the trace preventing convex loop shapes, there shouldn't be false-positive impossible paths where both the destination and starting node are in the same trapped island of valid nodes.

Gonna post updates when I tackle this further.

[applebus]

Any luck?

[SnpM]

I'm going to tackle this later potentially when we get to map designing + building placement in Desert RTS as I don't have any gameplay to test this with atm.

[LumpySpoon]

Just a thought, you could group the nodes, assign the group with a name. If the unit is in group1 he could not travel to group2. To group them you could, in a loop, assign nearest nodes to group1. And if there is are any unassigned nodes start the loop again and just assign them to another group.

[SnpM]

Hierarchichal pathfinding is a great solution that cuts down on processing time for general paths as well.

The problem is its complexity to implement, especially for a dynamic grid system.

I'm going to look into it.

[SnpM]

Cutting down on large feature development plans.