Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

AppGameKit Classic Chat / How to get around obstacles

Author
Message
Blendman
10
Years of Service
User Offline
Joined: 17th Feb 2014
Location: Arkeos
Posted: 26th Dec 2014 16:43
Hi

I make a little RTS game (sort of clash of... game), and I'm looking for a way to get around obstacle.
I have tried a pathfinding, but with 50 ennemies, it's a few slow ^^.

So, what i would to know : is there a way to make that :


I know that I can do it with pathfinding Astar (I have find one example), but as I said, with 50 ennemies, its too slow.
I have thinking about a sprite for the obstacle-shape (made with SetSpriteShape()) and test the collision between this sprite and the sprite shape of the characters with GetSpriteCollision(player, spriteShapeForHouse)



If you have an idea

http://www.dracaena-studio.com
Impetus73
13
Years of Service
User Offline
Joined: 28th Aug 2011
Location: Volda, Norway
Posted: 26th Dec 2014 17:18
If the character hits a sprite/house, force it to only be able to move in certain directions, so that it can not go through it.

----------------
AGK programmer
Did Amiga / AMOS programming in the 90's.
MikeHart
AGK Bronze Backer
21
Years of Service
User Offline
Joined: 9th Jun 2003
Location:
Posted: 27th Dec 2014 01:56
Besides blocking the nodes where the enemies are, what is it that enemies make the pathfinding slow?
Markus
Valued Member
20
Years of Service
User Offline
Joined: 10th Apr 2004
Location: Germany
Posted: 27th Dec 2014 18:51 Edited at: 27th Dec 2014 18:51
i have some source code, its similar a fluid, in runs from up to down.
means u have a list and the point that is lower your current height goto target.





AGK 108 (B)19 + AppGameKit V2 Alpha .. : Windows 8.1 Pro 64 Bit : AMD Radeon R7 265 : Mac mini OS X 10.10 (Yosemite)

Attachments

Login to view attachments
Naphier
14
Years of Service
User Offline
Joined: 2nd Oct 2010
Location: St Petersburg, Florida
Posted: 28th Dec 2014 03:27
"Raycast" from the point of the enemy sprite then rotate the ray clockwise 45 degrees (or smaller) until a hit with the object does not occur.
For example:
enemy.position = 10,10
enemy.velocity = 1,0
test sprite hit at 11,10
if true then set y velocity + 1 until the ray no longer hits
you'd also need to store the original position and velocity so that you can keep testing to see if the enemy can return to it's original track.
Does that make sense?

george++
AGK Tool Maker
17
Years of Service
User Offline
Joined: 13th May 2007
Location: Thessaloniki, Hellas
Posted: 28th Dec 2014 10:54 Edited at: 28th Dec 2014 11:57
Here is my approach:
The p0 is the position of the guy who wants to avoid the obstacle
The p1 is the position of the obstacle
The p2 is the position of the destination in order to avoid the obstacle
The b/2 is the size of the obstacle
The v is the distance of how much the guy will go away from the obstacle
All you need is the calculation of p2 having a parameter v:



I didn't test it, but I hope that will work with efficiency in terms of speed
Markus
Valued Member
20
Years of Service
User Offline
Joined: 10th Apr 2004
Location: Germany
Posted: 28th Dec 2014 11:23 Edited at: 28th Dec 2014 11:25
one obstacle is not a problem, but what if you have a fence?

@george++
+1 for the explanation

AGK 108 (B)19 + AppGameKit V2 Alpha .. : Windows 8.1 Pro 64 Bit : AMD Radeon R7 265 : Mac mini OS X 10.10 (Yosemite)
janbo
16
Years of Service
User Offline
Joined: 10th Nov 2008
Location: Germany
Posted: 28th Dec 2014 20:22 Edited at: 28th Dec 2014 20:40
Hi I would suggest the same as markus.. using a floodfill kind of Pathfinding algorithm:Good explanation of "Best-first search" algorithm

I's the best for one target.
Just update the list if the target position changes.
If you have more targets then think of layers...and switch between them.


If you want to use A* then I would determine a leader and just calculate the path for him, let the others follow him and use an avoidance algorithm on them...
Obstacle Avoidance steering behavior

Blendman
10
Years of Service
User Offline
Joined: 17th Feb 2014
Location: Arkeos
Posted: 30th Dec 2014 13:57 Edited at: 30th Dec 2014 13:59
HI

Thank for your answer.
As Marcus said, I have in some map fence, wall or barrier.


@janbo : Im' very interested about your pathfinding example . I have test another pathfinding example (made by phallax). it's great but not for a lot of ennemies ^^.

The difficulty is to move between building (which should be possible).

Here is a screenshot ingame of my game :

Some of the possible path are in red, the characters should move between building but get around the wall.

I think I could use a method to test the collision between character and the sprite of the "ground collision" (which is invisible in this screenshot), and for the wall it's a 64*46 block, but not for the other building (the sprite for collision is smaller)

http://www.dracaena-studio.com
janbo
16
Years of Service
User Offline
Joined: 10th Nov 2008
Location: Germany
Posted: 30th Dec 2014 15:49 Edited at: 30th Dec 2014 22:09
For the pour pathfinding you will need a smaler grid or a larger gap between the buldings (what I can see on the screenshot)

I'll send you the demo code (via TGC chat)
• 2000 enemys moving on a different path to the same target
• 100 fps on a 20*20 Grid

I think drawing 2000 enemys is what is slowing the fps, you calculate path for every Grid tile to the target once then every enemy looks on his current position wich neighbour is this next local target.
(I'm sure you know what I'm talking about..but please ask me if you want)
The rest should run as fast as it can draw all your stuff.
I can't think of a faster method for pathfinding if you want every enemy to have his own path.
A* for one leader and avoidance algorithm for the follower might be faster but is tricky RTS stuff

After writing this post I tested the time for calculating the path:
• 20*20 grid = 0.000280 sec
• 200*200 grid = 0.543812 sec

Old i7 overclocked to 3.6 Ghz
Nvidia GTX970
6 GB DDR3 [need to update that ]

Conjured Entertainment
AGK Developer
19
Years of Service
User Offline
Joined: 12th Sep 2005
Location: Nirvana
Posted: 1st Jan 2015 03:07
Quote: "Here is a screenshot ingame of my game : "

I see you already have help for your path finding challenge, but I couldn't resist commenting on that screen shot because I love those graphics. That is some crazy cool artwork.

Login to post a reply

Server time is: 2024-11-25 14:34:59
Your offset time is: 2024-11-25 14:34:59