"Pathfinding" without using Pathfinding

To explain I posted everything in the diagram below.

I'm attempting to make something like a Real time pathfinding if you will only using lines and points except this one forecasts your character/sprites' position every tick which obviously cannot be applied using the built in pathfinding function.

Key point #1: It doesn't matter if the character can't fit through the walls; what matters is the shortest distance can be found immediately.

Key point #2: Might export this using C3 so I'd prefer it done using VANILLA plugins

I'm thinking I'm going to need 3 sprites just to serve as points for each intersection on a wall and a single line sprite whose width will increase and until it reaches destination or until max distance is reached. To explain check out my "Hypothetical Solution" section at the bottom of the picture posted.

This is the solution I though of however I'm having trouble actually applying it. I'm thinking something like:

[repeat 180 times]

[point 1 is overlapping wall] set point 1 angle to [point1.angle + 1]

or something like that but to be quite honest I don't know where to start.

Thank you.

What if there are two or more walls? How do you choose the closest route? This could be a very difficult task.

Why don't you use the Pathfinding behavior? I understand you want to show the path in real time, but pathfinding works fast.

See this example:

https://www.dropbox.com/s/jocoq56vsfkg3 ... .capx?dl=0

I'm working on a visibility graph based pathfinding algorithm, no idea when I'll be done with it though. It trades off reduction of the number of nodes for an increase in the number of edges. In scenarios where fewer nodes are visible to each other the benefit will be more pronounced. It will not work well for large open spaces or long corridors. There is also additional work to be done putting image points at all "wall" sprite corners, since we don't have access to collision box expressions.

ref: http://theory.stanford.edu/~amitp/GameP ... tions.html

If you're interested in looking into it yourself rather than waiting for when I may or may not get it done.

But definitely try the built in pathfinder first, you might be surprised. Remember, you don't actually have to run pathfinding every tick - you can update just the visual feedback for the user, which doesn't necessarily have to be instantly accurate. Basically there are methods to "hide the lag", like with netcode.

What if there are two or more walls? How do you choose the closest route? This could be a very difficult task.

Well that's the thing, I want there to be a max of 2 turns and actually want the line to be displayed that way for a visual representation of the max distance. Basically what's shown in the picture is exactly how I want it to look like. The cursor is constantly projecting the destination and calculating distance like that.

Have yet to check your example since I haven't updated versions yet but will check tomorrow.

I'm working on a visibility graph based pathfinding algorithm,

VERY interesting. I actually thought of a solution using 2 sets of lines sprites to measure X and Y displacement and simply projecting my desired path along the Hypotenuse.

Not as complex as yours but it's something I can work with. Still looking forward to your solution.

MPPlantOfficial

To open my capx saved in a later version, upzip it to a folder, open .caproj file in Notepad and edit this line:

<saved-with-version>25703</saved-with-version>

For example, if you have version 255, change it to:

<saved-with-version>25500</saved-with-version>

I've had luck in the past doing instant path finding in the past by utilizing the LOS behavior.

It's similar to oosyrag's idea but works with simpler maps of just isolated boxes.

It works by first placing corner objects at the corners. Then the objects either move to the goal if it has LOS, or it goes to a corner sprite it has LOS to. I also believe it did some checking to see which corner was closer to the goal, but it's been a while since i looked at it.

My following code is in need of improvement since objects get stuck, and you could manually place corner objects instead of automatically moving it if need be.

I'll probably putter around and see if i can come up with something closer to your op. It seems interesting.

I've had luck in the past doing instant path finding in the past by utilizing the LOS behavior.

Awesome, R0j0! Nice touch on the corner sprites.

That seems to be exactly what I needed for my Right triangles solution.

https://www.dropbox.com/s/sjqzzgvqplk4w ... .capx?dl=0

...and as another behaviorless example there is this:

https://www.dropbox.com/s/aondowy4ycjgl ... .capx?dl=1

Click drag to mark start and end points.

I took dop2000's map, added in the event based astar shortest path search i've made previously, added some setup events to generate nodes at the corners of the walls, and then finally did an event based los to create a connection graph.

It works pretty well, I thought it would be slow. There are a few things that could be done to improve it.

* The corners can be moved closer in. Too close may cause issues with the los and generation though.

* Only unrotated boxes work for walls with this. Rotated boxes or arbitrary polygon shapes can be done. The generation and cleanup of the nodes in setup would need to be modified.

* The mesh is kind of ugly, so another idea is to build in an editor in the game to be able to give more manual control if need be. Tweaking the whole thing to be more navmesh like would be nice.

Anyways, that was fun.

cheers

...and as another behaviorless example there is this:

https://www.dropbox.com/s/aondowy4ycjgl ... .capx?dl=1

Click drag to mark start and end points.

I took dop2000's map, added in the event based astar shortest path search i've made previously, added some setup events to generate nodes at the corners of the walls, and then finally did an event based los to create a connection graph.

It works pretty well, I thought it would be slow. There are a few things that could be done to improve it.

* The corners can be moved closer in. Too close may cause issues with the los and generation though.

* Only unrotated boxes work for walls with this. Rotated boxes or arbitrary polygon shapes can be done. The generation and cleanup of the nodes in setup would need to be modified.

* The mesh is kind of ugly, so another idea is to build in an editor in the game to be able to give more manual control if need be. Tweaking the whole thing to be more navmesh like would be nice.

Anyways, that was fun.

cheers

I hope you keep working at this. What exactly can be done with this in regards to having sprites move along the path one draws out?

Pathfinding and movement are separate systems.

Rojos function gives you a path in the form of node uids in order. To use it for movement, you can save the list to a movement array, and have a sprite move to each node in sequence with your preferred method of movement. It may be better to write only the x and y position of the nodes to the array, as the start and end node objects may not be there for the duration of the movement.

YoHoho

The astar search function returns a list of the uid's of the nodes making up the path. I implemented moving before here:

I think i came up with a cleaner way, so i updated the capx above in this topic, as well as added some more comments.

YoHoho

The astar search function returns a list of the uid's of the nodes making up the path. I implemented moving before here:

I think i came up with a cleaner way, so i updated the capx above in this topic, as well as added some more comments.

Works great with boxes, but not good with curves. I expect that the editor you mentioned might be useful when dealing with such things. Very interesting - need to play a bit more.

zenox98

You mean curves with the walls? It was only made with unrotated boxes in mind at the moment.

Edit:

Updated it to work with rotated boxes. The cleanup stage to reduce the points doesn't work as well though.