Pathfinding is weird - any alternatives?

Discussion and feedback on Construct 2

Post » Fri Apr 03, 2015 3:42 pm

Hey,

So I'm doing some stuff with pathfinding, and I'm noticing couple of very irritating things about it:

1. The delay before movement
2. Weird occasional "turning", that cannot be turned off.

Do you know any alternative approaches that work better?
My professional Royalty Free Music at Scirra Assets Store
--------------------------------
Specs: i5 2500, 16gb of ram, gtx 770, win 7, Focusrite Scarlett 8i6, Mackie mr8mk2, Alesis 320, browsing the net on chrome.
B
73
S
20
G
19
Posts: 1,931
Reputation: 17,084

Post » Fri Apr 03, 2015 6:09 pm

1. The delay is unavoidable. Path finding can take a while.

There are other methods but they depend on what you want to do.

A* (a star) is what the pathfinding behavior uses and is the general purpose solution for simply finding a path as fast as possible. The "turning" can probably be avoided by doing the motion manually using the path points the behavior gives. If you roll your own with events then you could do things to make the delay shorter by exploiting the design of your levels.
Like say your game consists of rooms then you could do a lower resolution search of just the path from room to room and then find a more detailed path for each room you move through. And on that note you might be able to do a progressive pathfind by doing a search on a coarse grid first and then perhaps using progressively finer grids.
Also as a note, if you roll your own you could also use something besides a grid, like line segments for pathfinding to reduce the number of nodes to search through.

Dijkstra's algorithm is another, which is slower but gives you the path from all grid cells to one or more points. It basically is a flood fill that starts at the destination then expands to the neighboring cells and stores the direction to move to get to the beginning cell. This is repeated until all the cells are visited. Then the moving sprites just need to use the direction of the cell they are currently on to know which way to move. Basically the path is only calculated once.

I have an example here:
viewtopic.php?f=147&t=115386&p=835820&hilit=Dijkstra#p835820

For completely delay free pathfinding you could pre-calculate the path from every point to every other point.
This guy did just that:
quadralant-span-class-posthilit-path-span-span-class-posthilit-finding_p632343?#p632343
The disadvantage is it's tedious to setup, but once it is the pathfinding will take no time at all. The cells are pretty big, but the idea is to just get the enemies in the general area and then use something simpler to move toward the player's exact position.
B
84
S
27
G
70
Posts: 4,924
Reputation: 49,540

Post » Fri Apr 03, 2015 6:40 pm

@R0J0hound Hi, thanks for the extensive reply. I'm doing something similar to syndicate with a difference that you can select 4 agents like in rts. I just looked at quads example, but not sure how this could be implemented with my game. Any more suggestions will be highly appreciated! Meanwhile I'll look at Dijkstra example.


EDIT@ I looked at second example, and it is really cool, but not sure if it what I currently need.
My professional Royalty Free Music at Scirra Assets Store
--------------------------------
Specs: i5 2500, 16gb of ram, gtx 770, win 7, Focusrite Scarlett 8i6, Mackie mr8mk2, Alesis 320, browsing the net on chrome.
B
73
S
20
G
19
Posts: 1,931
Reputation: 17,084

Post » Fri Apr 03, 2015 7:06 pm

The delay often comes from

1. too low rotation speed, set the Rotate speed of Pathfinding to something like 360 * 4
2. too small cell size, try to make your cells as big as possible
B
11
S
2
Posts: 213
Reputation: 1,266

Post » Fri Apr 03, 2015 7:35 pm

Chupup Games wrote:The delay often comes from

1. too low rotation speed, set the Rotate speed of Pathfinding to something like 360 * 4
2. too small cell size, try to make your cells as big as possible


Setting rotation to high speed worked!

But, there is several of other issues:
1. for some reason object cuts corners, which tells me that polygoal collisions are not taken under consideration, right?
2. It is easy to break the behaviour, where when object is doing corner, you keep on clicking, then it will get stuck on it.
3. There are still weird movement bounces, when object is next to the wall, and you change its direction, by clicking anywhere opposing to its movement.
4. when object moves next to a isometric wall, it slightly bounces.

capx http://drive.google.com/file/d/0B0jUjWN7LcQhbGE5STVXNUNoX2c/view?usp=sharing
My professional Royalty Free Music at Scirra Assets Store
--------------------------------
Specs: i5 2500, 16gb of ram, gtx 770, win 7, Focusrite Scarlett 8i6, Mackie mr8mk2, Alesis 320, browsing the net on chrome.
B
73
S
20
G
19
Posts: 1,931
Reputation: 17,084

Post » Fri Apr 03, 2015 7:38 pm

You possibly could get away with doing something much simpler for a game like that. Most of the moves have a line of sight to the players and the obstacles look to be mainly just rectangles with no crevices.

You could use line of sight and just move forward if the player has a clear view. If there is an obstacle in the way then just pick the furthest corner of the building that the player can see an move toward that, then they can continue to the goal as they round the corner. This should be able to work with many buildings, but the beauty of it is the player only addresses obstacles as they see them.

It's simple and fast but can fail if you have alleyways instead of just buildings. I could be acceptable though, as I've played games where I had to help the player pick a better path. But now that I think of it you can mark the alleys in the editor so that the player can know to only go inside if the goal is in there. In a similar way you could mark long winding corridors I think, and just handle that in a unique way.

EDIT:
https://dl.dropboxusercontent.com/u/542 ... hfind.capx
B
84
S
27
G
70
Posts: 4,924
Reputation: 49,540

Post » Fri Apr 03, 2015 7:54 pm

@R0J0hound Very interesting concept! The bullet can get slightly confused when there is more objects. What puzzles me thought, is that it overlaps with the gray boxes representing buildings, even thought both objects are solid.

EDIT@ Would it be possible to connect your idea with pathfinding?! I think it is possible!
My professional Royalty Free Music at Scirra Assets Store
--------------------------------
Specs: i5 2500, 16gb of ram, gtx 770, win 7, Focusrite Scarlett 8i6, Mackie mr8mk2, Alesis 320, browsing the net on chrome.
B
73
S
20
G
19
Posts: 1,931
Reputation: 17,084

Post » Fri Apr 03, 2015 8:02 pm

Woah, I was just passing by
I fix an issue on my project
Thanks
B
71
S
20
G
10
Posts: 641
Reputation: 9,648

Post » Fri Apr 03, 2015 8:17 pm

@R0J0hound

But how would you go about avoiding smaller assets and moving npc?
My professional Royalty Free Music at Scirra Assets Store
--------------------------------
Specs: i5 2500, 16gb of ram, gtx 770, win 7, Focusrite Scarlett 8i6, Mackie mr8mk2, Alesis 320, browsing the net on chrome.
B
73
S
20
G
19
Posts: 1,931
Reputation: 17,084

Post » Fri Apr 03, 2015 9:08 pm

The player doesn't utilize the solid behavior, it's only used for the line of sight.
It could be re-worked to utilize astar so the shortest distance is used every time, but it would have to be astar done from scratch, since it wouldn't be grid based.

If smaller objects are passed through you could roll your own LOS with events with that in mind, or probably more appropriate implement some kind of collision response to push objects out of each other. Avoiding moving objects can be done by looking at where the objects will be a little in the future and if they are colliding adjust the current angle of motion so it won't.
B
84
S
27
G
70
Posts: 4,924
Reputation: 49,540

Next

Return to Construct 2 General

Who is online

Users browsing this forum: Google [Bot] and 3 guests