Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (482)
Games in Android Showcase (110)
games submitted by our members
Games in WIP (550)
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  
  Any tips for obstacle avoidance etc.?  (Read 7254 times)
0 Members and 1 Guest are viewing this topic.
Offline appel

JGO Wizard


Medals: 50
Projects: 4


I always win!


« Posted 2007-12-17 06:03:35 »

Seeking your wisdom  Grin

I have a tile based grid, and pathfinder that returns me a path of Nodes in a List. Everything works fine, but!

When I select 2 or more units and tell them to go to some tile, then they will all group together at the end and appear as ONE! They are all occupying the same tile.

This is of course a very old problem and has been solved kazillion times, so I don't want to invent a new solution kazillion+1 times. Please tip me off how I can solve this, maybe this is a very simple problem.

I was thinking about something like:
1. If unit has a path that it is following, verify that there are no obstacles in path. If there are obstacles get new path to goal node.
2. If goal node is occupied, find a new goal node that is the nearest unoccupied node to the original goal node.

But doesn't seem to be working.. :| maybe I did this wrong.


Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline BloodRain

Junior Member





« Reply #1 - Posted 2007-12-17 11:54:31 »

Try Lee's algorithm . A faster,but a little harder is Dijkstra's algorithm . Google for these ... Wink
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 781
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #2 - Posted 2007-12-17 13:07:45 »

Increase the cost for planned / recently traveled nodes and their immediate surroundings.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline appel

JGO Wizard


Medals: 50
Projects: 4


I always win!


« Reply #3 - Posted 2007-12-17 14:08:43 »

Increase the cost for planned / recently traveled nodes and their immediate surroundings.

Sounds better the more I think about it, might be some problems with this, but I'll try this.

But "Immediate surroundings"? Like for every node in the path I shall increase the cost of all its neighbouring nodes also?

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline SimonH
« Reply #4 - Posted 2007-12-17 16:29:29 »

You could use a reservation table - see here (there's some other ideas there too)

People make games and games make people
Offline appel

JGO Wizard


Medals: 50
Projects: 4


I always win!


« Reply #5 - Posted 2007-12-17 16:37:21 »

You could use a reservation table - see here (there's some other ideas there too)

Great link, thanks Smiley

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 781
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #6 - Posted 2007-12-17 21:36:28 »

Sounds better the more I think about it, might be some problems with this, but I'll try this.

But "Immediate surroundings"? Like for every node in the path I shall increase the cost of all its neighbouring nodes also?

Yup, to spread the units naturally, but keep them kinda grouped at the same time.

If you've ever played Cossacks, you might have noticed the wonderful AI. They used cost-algorithms that did not only take terrain into account, but also their own and the enemies 'influence'. Just as much as they attract eachother, they will repell.

Just take the average walk on the street, you can pretty much visualize the influences and the 'logical' path you travel through people moving at different speeds and in different directions. You don't need interconnected nodes, just a couple of Vec2[128][128] and Vec1[128][128] for different kinds of influences, which will influence (yet again) the travel-cost through the nodes.


Note:
I've never implemented this myself, hardly any pathfinding, except quite fancy gridbased floodfill. So if there are giant practical problems, don't blame me Smiley

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 781
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #7 - Posted 2007-12-17 21:53:38 »

To clarify a bit:

When a lot of units travel South-West to North-East, the influence-map for 'moving in that direction', becomes stronger and stronger. That way you won't see any (of your own) units moving *through* your formations, they'll try to avoid and walk along side.

Calculate the impact by: unit-heading DOT map-influence-vector


Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline appel

JGO Wizard


Medals: 50
Projects: 4


I always win!


« Reply #8 - Posted 2007-12-26 12:24:57 »

Maybe I explain what I finally did.


I basically decided that obstacle avoidance (e.g. avoiding going through/over other units) was a waste of time, so units can now travel over each over.

I however made the game so units don't share the same tile! So if I were to select and tell a number of units to go to the same tile location, they would not end all on the same tile. I added a "reserved" boolean in my "Tile";
1. The first (to run in the program) unit sets the goal tile as reserved, and a path is found between start and goal.
2. The 2nd unit sees the goal tile is reserved, and now I use Dijkstra to find the nearest tile (new goal) that is not reserved and reserve it for that unit, and find a path between the start and the new goal location.
3. The 3rd unit and up does exactly the same as the 2nd unit.

It's very nice and works! Smiley

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 781
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #9 - Posted 2007-12-26 14:06:58 »

I basically decided that obstacle avoidance (e.g. avoiding going through/over other units) was a waste of time, so units can now travel over each over.

[...]

It's very nice and works! Smiley


And if you give your game a magic-theme, you can get away with it. Tongue

Not so much a technically outstanding achievement Wink

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline darkprophet

Senior Member




Go Go Gadget Arms


« Reply #10 - Posted 2007-12-26 15:05:07 »

The simpler and more intuitive solution to the problem the more time you can waste debugging something else Wink

DP Smiley

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Offline appel

JGO Wizard


Medals: 50
Projects: 4


I always win!


« Reply #11 - Posted 2007-12-26 16:52:56 »

And if you give your game a magic-theme, you can get away with it. Tongue

Hehe... well, it was either that or spend all my holiday vacation studying flock movement, sharing of paths and unit cooperation of moving (e.g. in narrow corridors).

I simply redefined the problem Smiley I'd rather have something work than nothing. Besides, I can always revisit this problem later. My game isn't a commercial one anyway.


Not so much a technically outstanding achievement Wink
My achievement Wink

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline DzzD
« Reply #12 - Posted 2007-12-26 18:37:51 »

maybe you already know or dont care about your problem anymore, but here is an idea :
for each tile define an occupied or not state with a time (or a num turn or a num frame) if turn based using a 3D array.

so basically the problem get one more dimension, use a 3D array for path finding, the third dimension represent time (or turn or frame). so when you look for a path you look in the 3d array, when you select a path you put it in the 3d array as occupied.

NB: your 3d array must loop to avoid a two huge third dimension.

dont know if I well explain myself  Sad, but hope it is undestandable as it may be pretty simple to implement.

this solution have advandage of taking care of unit speed and is very easy to implement and understand, also I guess it should work perfectly  Wink.

Offline Mr_Light

Senior Member




shiny.


« Reply #13 - Posted 2007-12-26 22:54:27 »

random idea:

group units that travel to the same place.

model the group as a drop of liquid.

make the liquid change shape by changing the formation of the units accordantly and as necessary to move though the obstacles. perhaps even breaking of in two parts.

It's harder to read code than to write it. - it's even harder to write readable code.

The gospel of brother Riven: "The guarantee that all bugs are in *your* code is worth gold." Amen brother a-m-e-n.
Offline appel

JGO Wizard


Medals: 50
Projects: 4


I always win!


« Reply #14 - Posted 2007-12-27 11:52:11 »

random idea:

group units that travel to the same place.

model the group as a drop of liquid.

make the liquid change shape by changing the formation of the units accordantly and as necessary to move though the obstacles. perhaps even breaking of in two parts.

Sounds like you're inventing a new problem to me Smiley

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline Mr_Light

Senior Member




shiny.


« Reply #15 - Posted 2007-12-27 23:29:13 »

yes which leaves you with two problems instead of one but both are simpler to solve as a whole then the other. added benefit is that units behave more natural: they stck together yet spread out enough to overcome obstacles. it is also makes more sense when the enemy clashes upon one an other an additional feature is that you can implement differed formations easier. I'll see if i can reserve some time to whip something up, before I pass it on as advise.

It's harder to read code than to write it. - it's even harder to write readable code.

The gospel of brother Riven: "The guarantee that all bugs are in *your* code is worth gold." Amen brother a-m-e-n.
Offline t_larkworthy

Senior Member


Medals: 1
Projects: 1


Google App Engine Rocks!


« Reply #16 - Posted 2007-12-31 02:33:34 »

Quote
model the group as a drop of liquid.
Cheesy Just a simple implementation of the Navier-Stokes equations, rememeber to use semi-Lagrangian methods so it runs in realtime. Peice of cake

Runesketch: an Online CCG built on Google App Engine where players draw their cards and trade. Fight, draw or trade yourself to success.
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.

CopyableCougar4 (14 views)
2014-08-22 19:31:30

atombrot (28 views)
2014-08-19 09:29:53

Tekkerue (25 views)
2014-08-16 06:45:27

Tekkerue (23 views)
2014-08-16 06:22:17

Tekkerue (15 views)
2014-08-16 06:20:21

Tekkerue (22 views)
2014-08-16 06:12:11

Rayexar (61 views)
2014-08-11 02:49:23

BurntPizza (39 views)
2014-08-09 21:09:32

BurntPizza (31 views)
2014-08-08 02:01:56

Norakomi (37 views)
2014-08-06 19:49:38
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!