Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (498)
Games in Android Showcase (114)
games submitted by our members
Games in WIP (563)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  pathfinding for multiple objects?  (Read 4082 times)
0 Members and 1 Guest are viewing this topic.
Offline kappa
« League of Dukes »

JGO Kernel


Medals: 77
Projects: 15


★★★★★


« Posted 2006-01-30 16:29:37 »

i've had a look at path finding for a single unit and its not too difficult to get it round a map with static objects but what i'm having problem with it multiple units. i've tried adding units as obsticles on the map but since they move around this approach doesn't really work well (and pretty processor intense too) couldn't really find much information on this topic any pointer as to how this would work?

also if you have a squad of units moving them without colliding with each other is tricky too any idea's how you would tackle such a problem?

thx
Offline darkprophet

Senior Member




Go Go Gadget Arms


« Reply #1 - Posted 2006-01-30 18:27:40 »

You have to treat time as a 4th dimension into your equations, factoring *when* the two objects will collide in the future if they do. Its complicated to say the least and there isn't much resources about it on the net...

My guess is to do your own little algorithm Smiley

DP

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Offline darkprophet

Senior Member




Go Go Gadget Arms


« Reply #2 - Posted 2006-01-30 18:53:35 »

I was just reading through my old maths books and I stumbled upon "dynamic programming" for networks. It solves path finding problems locally instead of traversing the entire graph...

That lead me to the thought of why not have a radius in which you path find around in? The point you want to go to is the distance between the player and the goal clamped to the radius. Its less costly (less nodes to traverse), more realistic (limited range of sight) and you can probably do cool stuff with that too....

DP

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline arne

Senior Member




money is the worst drug- we should not let it rule


« Reply #3 - Posted 2006-01-30 21:12:26 »

I was just reading through my old maths books and I stumbled upon "dynamic programming" for networks. It solves path finding problems locally instead of traversing the entire graph...

That lead me to the thought of why not have a radius in which you path find around in? The point you want to go to is the distance between the player and the goal clamped to the radius. Its less costly (less nodes to traverse), more realistic (limited range of sight) and you can probably do cool stuff with that too....

DP

But this could lead to the units to stop at some local minimum, or only move between two points and not reach the target, even if there is a way. And you'll also have to respect, that objects are moving and that is sometimes wiser to simply wait until they can go, instead of turning immediately. Maybe this could solved by adding some weighted random decisions for the unit, to decide which way it should go. This way it will probably never go the shortes way, but it will reach it's target some day. It would also make it look more natural.

:: JOODE :: Xith3d :: OdeJava ::
Offline darkprophet

Senior Member




Go Go Gadget Arms


« Reply #4 - Posted 2006-01-30 23:09:52 »

If thats the case occurs whereby the actual goal hasn't been reached and there are no valid paths, then increase the search diameter....

Age of Methodology introduces the idea of "uni weights" whereby the units are infact allowed to overlap (very slightly), but the unit with the lesser weight during a collision moves out of  the way. I suppose the weight is dynamically calculated by the number of units selected, formation, how hard it is for the unit to move (cannon VS soldier)...etc

You could always treat the local lines that intersect with the current diameter of search as "rays" and collide those rays with the rays from the current target, where a point of collision occurs, then recalculate the path for that "ray" (i.e. put a kink in that ray making it two rays or something...). If there is no way around that (i.e going through a valley or a door way), then recalculate for the rays that are before and after the current ray....etc.

IMO, this looks more natural as you can see the object coming towards you, you know your going to hit it, but you only alter the path of movement until you actually collide with the object! Give the dudes some intelligence, they can clearly see a cannon coming towards them, so move out of the way before the cannon hits you...

DP

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Offline EgonOlsen
« Reply #5 - Posted 2006-01-31 22:35:29 »

Here's what Paradroidz (http://www.jpct.net/paradroidz) does to deal with this:

The calculations are grid based even if the game is actually presented in 3D. An entity is always located on a grid and has a global and a local target position on the grid. The target positions come from the path calculated by a modified A*-approach with taking only static obstacles into account. The global target position is the destination...it doesn't really matter in the calculation until it has been reached. The local target position is a position next to the actual position. If it's reachable, i.e. no other moving entity covers that position OR has it as a target position itself, the entity will move towards the midpoint of that position (in 3D) (with a slight chance to do something completely different to add a random element). If the target position is occupied (or most likely will be in the foreseeable future) by another entity, the next target position will be the exact opposite (compared to where the entity is now) of that position. That way, the entity tries to move out of a collision and resumes to travel its actual path only after it has reached this escape position. If the escape position is occupied too, it chooses a completely different global target.
Because the movement is done in 3D (at least when the entity is visible) and a grid is only a rough approximation of the actual position in 3D, a 3D ellipsoid collision detection acts as the last line of defense. Its outcome may change the grid position of the entity when it forces the entity to cross grid borders, but that doesn't matter. In the next iteration, it tries to reach its current local target from there.

Edit: That's how it basically works. There are some special cases that i had to cover, but that's really quite dependent on the game.
Edit2: Don't overcomplicate things. Often a simple "hack" can produce results that are "good enough", but again, this depends on the game.

Offline HamsterofDeath

Junior Member




Java games rock!


« Reply #6 - Posted 2006-05-05 14:53:41 »

i have a similar problem. my virtual frog/spaceship/whatever wants to get through a street full of cars/an asteroid field/whatever. i can calculate the position of any object at any moment in time, because the movement is pretty simple. my idea was to use the a*-algorithm, but alter the world after every step. i didn't try it yet, but it should work. this is pretty similar to brute-forcing a chess game, btw. the "world", and "other movable objects" are changing their states also.

as for the "but i have 200 units and therefore need a billion years for this calculation"-problem, i'd simply define a leader and let the others follow him.
Offline darkprophet

Senior Member




Go Go Gadget Arms


« Reply #7 - Posted 2006-05-05 22:01:12 »

The real problem that kappa was having was that other moving objects should block other objects without the need to recalculate the path everytime...Im not sure that A* solves that problem

DP

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Offline appel

JGO Wizard


Medals: 51
Projects: 4


I always win!


« Reply #8 - Posted 2006-05-05 22:06:22 »

If you have have let's see 50 units selected, and tell them to go to a place, you shouldn't calculate the path 50 times in one game-cycle.

Create a queue, and this queue would calculate maybe 1 path every 1-2-3 cycles, spreading out the calculations over 1-2 seconds. The player doesn't notice it.

Check: http://www.policyalmanac.org/games/aStarTutorial.htm

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

BurntPizza (19 views)
2014-09-21 02:42:18

BurntPizza (13 views)
2014-09-21 01:30:30

moogie (14 views)
2014-09-21 00:26:15

UprightPath (25 views)
2014-09-20 20:14:06

BurntPizza (27 views)
2014-09-19 03:14:18

Dwinin (40 views)
2014-09-12 09:08:26

Norakomi (73 views)
2014-09-10 13:57:51

TehJavaDev (96 views)
2014-09-10 06:39:09

Tekkerue (49 views)
2014-09-09 02:24:56

mitcheeb (70 views)
2014-09-08 06:06:29
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!