Raycast based Pathfinding.

Discuss game development design and post your game ideas

Post » Wed Oct 12, 2016 11:00 am

This was just an theory i had to try to create an alternative pathfinding, that doesn't always take the shortest way, but has a little bit of randomness to it. I just wanted some feedback if this would be a good approach and maybe some way on how to improve it. Hopefully it will be quite lightweight as well as it can be called in a function each time the NPC reaches one waypoint.

It's basically built on a raycaster that works in 2 steps. First step just calculates the next impact point, towards the target, next step creates 2 rays that rotates either clockwise or counterclockwise, then shortens that ray to the next edge of the impact point.

Image

1. I use a normal raycaster to determine the next impact object, and get a distance to the next casting point (black circle).

2. Two new rays are cast, which instead of shortening, rotates towards a few degrees the next angle that doesn't have impact. After an angle is found that doesn't have any collisions, the ray length is adjusted to edges of the impact object, and determines 2 points to where the character can go. (Green arrows). The character picks one of these 2 positions and moves there.

3. in this case the character picked the red path, so when he reach that point the raycaster triggers again. Same as #1 in the image. A ray is cast towards the destination point.

4. The new impact point creates two new rays that rotates again towards the next angle without colission, and adjusts the lenght. But here comes the tricky part. Do i adjust the length of the rays to be where the green arrows show?, since the character can't move through the blocking object?

Any ideas on how to improve this?
Follow my progress on Twitter
or in this thread Archer Devlog
B
41
S
18
G
18
Posts: 1,024
Reputation: 13,345

Post » Wed Oct 12, 2016 11:32 am

It's not going to work well when in close proximity to corners.
Image ImageImage
B
170
S
50
G
179
Posts: 8,378
Reputation: 113,425

Post » Wed Oct 12, 2016 11:35 am

newt wrote:It's not going to work well when in close proximity to corners.


Why would that be? If the ray is wide enough (wider than the character) it would detect overlap even on corners.
Follow my progress on Twitter
or in this thread Archer Devlog
B
41
S
18
G
18
Posts: 1,024
Reputation: 13,345

Post » Wed Oct 12, 2016 11:44 am

Well that's just it, the ray only needs to be half as fat as the character to see past the corner.
In order to work you would need to implement a cell border like C2 uses.
Keep the object from getting close to corners.
Image ImageImage
B
170
S
50
G
179
Posts: 8,378
Reputation: 113,425

Post » Wed Oct 12, 2016 5:48 pm

Why not something straightforward simple like this ?

https://www.dropbox.com/s/sa7qr6bjf8eal ... .capx?dl=0
B
33
S
18
G
28
Posts: 2,493
Reputation: 20,950


Return to Game Development, Design & Ideas

Who is online

Users browsing this forum: No registered users and 0 guests