Suggestion: Collision Avoidance Behavior

Discussion and feedback on Construct 2

Post » Tue Sep 30, 2014 2:45 pm

Hello,

@Ashley

Current pathfinding is way too much calculations for multiple units on the screen and it doesn't work well with moving obstacles. But there's a solution called Collision Avoidance, which is actually not that complex to implement.

http://gamedevelopment.tutsplus.com/tutorials/understanding-steering-behaviors-collision-avoidance--gamedev-7777

And here: http://www.math.u-psud.fr/~maury/paps/foules/a_model_of_human_crowd_behavior__group_i_378448.pdf

Here's a js library: https://github.com/palmerabollo/rvo2-js

Units have a target position, they try to evade closest threats/obsticles while moving to the target.

I'm trying to implement it with events, but it gets pretty clunky with some picking corner cases.
Last edited by xoros on Mon Oct 13, 2014 9:39 am, edited 1 time in total.
B
45
S
11
G
4
Posts: 517
Reputation: 7,393

Post » Mon Oct 13, 2014 9:38 am

@Ashley can you please elaborate on the subject? I tried to implement a simple collision avoidance with events, but that ended up with so much hacking around with picking instances of the same type, very cluttered logic and bad performance.

This one is an interesting approach based on Diffusion/Heatmaps:
http://gamasutra.com/blogs/TylerGlaiel/20121007/178966/Some_experiments_in_pathfinding__AI.php

Vector field pathfinding:
http://gamedevelopment.tutsplus.com/tutorials/understanding-goal-based-vector-field-pathfinding--gamedev-9007
B
45
S
11
G
4
Posts: 517
Reputation: 7,393

Post » Mon Oct 13, 2014 1:33 pm

This is an incredibly difficult problem to solve in general. It could also be very CPU intensive and slow down games. I'm not sure solving such a thorny and problematic feature is going to be high on our priorities. You could experiment with the plugin SDK and see if you can come up with something yourself.
Scirra Founder
B
395
S
232
G
88
Posts: 24,371
Reputation: 193,762

Post » Mon Oct 13, 2014 2:01 pm

Indeed, that's a hell of a problem. May be it's time to write my first plugin :)
B
45
S
11
G
4
Posts: 517
Reputation: 7,393

Post » Mon Oct 13, 2014 7:44 pm

If there was a way to visually link items and make directional graphs (with an arrow pointing towards the direction and two arrow heads for both directions [to avoid making two links in that case]), and you could query the node connectivity, one could more easily do path planning on the graph
B
14
S
2
Posts: 26
Reputation: 933

Post » Mon Oct 13, 2014 8:00 pm

Message: birbilis can only post plain text URLS until they have 500 rep. 1 URLS modified. Why?
btw, here (http://www.mech.upatras.gr/~robgroup/ol ... index.html) you can find a demo with source code (it was in Delphi [the algorithms are in the respective folder]) for various path planning algorithms you can use on a grid

don't remember if I had also implemented A* in that demo, probably not (I see it has BestFirst, BreadthFirst and DepthFirst)

UPDATE: it doesn't allow me to post URLs here, so replace the last part with
~robgroup/old_site/search/index.html
B
14
S
2
Posts: 26
Reputation: 933

Post » Mon Oct 13, 2014 8:10 pm

Another thing one should look for inspiration on designing behaviors is NetLogo. Has many amazing models in there
B
14
S
2
Posts: 26
Reputation: 933

Post » Mon Oct 13, 2014 8:33 pm

There is a Node path finder in the store. but unfortunately when I tried to work to make a plugin/behaviour to do on screen edit time path set up it can't really be done. There isn't enough interaction control in the IDE core system that's being used. So it's more likely a C3 feature. So right now it's CSV based graph path finder. I'm working on a runtime tool that will create, output and upload the graph. But it's not as convenient as an edit time tool :\ but i'm working on a few bits to fix up before that part is released.
B
90
S
18
G
9
Posts: 2,455
Reputation: 15,018

Post » Mon Oct 13, 2014 9:07 pm

sounds cool @jayderyu
B
87
S
44
G
16
Posts: 1,002
Reputation: 17,932

Post » Wed Oct 15, 2014 7:43 am

Great news @jayderyu
B
45
S
11
G
4
Posts: 517
Reputation: 7,393


Return to Construct 2 General

Who is online

Users browsing this forum: Sockratease, Yahoo [Bot] and 5 guests