How to temporarily force one way pathfinding

I am using a pointgraph (well, a custom graph derived from it; there is almost no difference from a pathfinding perspective).

All of my nodes are very simple, the only ever connect to two other nodes, plotting points on lines. Sometimes I need to pathfind in one direction or another. I am using this to trace the edges of roads in my game to allow the user to draw zones near them. as they move the mouse, I want to continue tracing the path in the natural direction to player has been dragging.

The problem is that if a player traces around a circle, eventually the outline will flip to the other side, because the path becomes shorter. I would like to enforce one way pathfidning temporarily. Is there an out of the box way to do this that doesn’t require breaking connections?


I’m afraid I don’t understand the scenario completely, a screenshot would help.
From what I understand, you just want the agents to follow a path that the player draws, but it doesn’t seem like pathfinding is required at all.

sorry, I’ll try to explain better.

Imagine a circle, where the path is simply the circumference of the circle. The player traces a path around the circle. They do this with a click and drag, so we keep track of where they clicked, and where the mouse pointer is now.

Using that start and end point, we find the closest point on the circle to each point (start and end from the mouse), then path find between those two points to get a perfect trace.

Once the start point, and the end point (from the mouse drag operation) becomes a 180 degree angle (using center of circle as a reference) which that they are on opposite sides of the circle, the path finding begins to flip to the other side because now that path is shorter. This is expected.

What I woudl like to do is enforce a constraint that basically says to continue to path find in the direction we started to pathfind from.

I figured the best way to do this would be to look ahead one PointNode, and temporarily set it to be one way so that pathfinding is impossible in the other direction, but just in that frame.

Does that make more sense? I was thinking one way would make sense, but maybe there is something else I can do to enforce the same constraint? Ideally something that does not require the entire graph to be updated (understood if it is required though).

Ok, however I don’t think this requires pathfinding in any way, it’s probably easier without pathfinding.
Is it only a circle you need to move around or is it a more complicated world?

It’s a more complicated world. I was just trying to simply it to explain it. I could be tracing something as complex as a person’s signature for instance; lots of unpredictable curves.

The real application of this is to allow a player to draw zones that are connected to roads. Think simcity, but with lots of unpredictable curves. They player draws a zone, and it hugs the outline of the nearby road(s). The pathfinder works beautifully for this (originally tried lots of collisions tests, but they proved to be too unreliable). There is just the one small quirk of the path “flipping” to the other side.

Also, if this is still hard to conceptualize, I can make a gif.

Ok, so you have some kind of road network, and the player draws a curve which roughly follows those roads, and you want to find the closest path of nodes to that curve? Or rather, I assume you want to smoothen it out a bit so that it removes unnecessary detours (which is why pathfinding is required).

If I understand it correctly, your road network is a general graph, so just specifying the direction at the start would not help you in more complicated scenarios (e.g a circle in the middle of the path). But I think an easy solution would be to split up the player drawn curve into pieces. So if the player drew a circle, it will first find a path to say 1/3 of the cirlcle, then 2/3 of the circle, then the full circle (1/3 and 2/3 are pretty arbitrary). Do you think that will work for your use case?

Sorry, I had moved on to other things in my project. haha. But your solution is fantastic. simple and does the job! I’ll let ya know if it works once I get back to that aspect of it. haha.

1 Like