Hi !
Featured games (90)
games approved by the League of Dukes
Games in Showcase (789)
Games in Android Showcase (234)
games submitted by our members
Games in WIP (864)
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  
  Interesting Pathfinding Question  (Read 5794 times)
0 Members and 1 Guest are viewing this topic.
Offline dayrinni

Junior Devvie

« Posted 2007-05-17 08:48:58 »

I have been playing around with the thought of doing path finding without a grid. Something like the swarm applet, but instead, you click on a point on the screen and the elements will move to that place, but not overlap as they move, as well as, no overlapping when they arrive to the spot, or close to it if they can't move all the way to the point. The only obstacles will be the units themselves, the map is open.

I have not given TOO much thought on this so I decided to come here and make a post and see if someone has attempted this and can give me some 2 cents. I am going to start planning it tomorrow as I am pretty tired.

So any ideas or thoughts on this idea?

Offline kappa
« League of Dukes »

JGO Kernel

Medals: 123
Projects: 15


« Reply #1 - Posted 2007-05-17 10:22:36 »

some nice applets that demonstrate steering and flocking behaviors over at
Offline dayrinni

Junior Devvie

« Reply #2 - Posted 2007-05-17 17:45:33 »

Those are some very nice demos. Thank you for showing them to me. There was a link to both a paper and to a C++ library, I will have to check both out and get back to you!
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline dayrinni

Junior Devvie

« Reply #3 - Posted 2007-05-18 02:45:42 »

Alright, lets see if I can get the logic down for this:

Case: I am moving an object in a field of other moving objects. The user decided where these objects are moving, like in a typical RTS game.
High Level Logic:
1.) During each tick of the movement cycle, I look at each object.
2.) When I look at each object, I see if anything will intersect during it's current direction.
  2.1.) I can do this by stepping through the future based on the current speed of both parties. If at any point they intersect, do something to avoid it.
  2.2.) To avoid the detected collision. I somehow have to choose what the two parties will do.
  2.4.) I want to ensure that objects never move faster than their max speed. Generally, the objects will always be moving at their fastest rate. This means that I have to deduce the time it will take the objects to reach their intersection point. I have already done this in 2.1. I can then calculate which one to slow based on the distance.

Problem: What if I detect more than 1 collision with the same object and then I decide to slow it when it's speed should not change? Example: Object 1, 2 and 3. Object 1 will have a collision with 2 and 3. Upon looking at the cases, in sequential order I determine the following:
Object 1 vs 2: Object 1 remains constant while Object 2 slows down.
Object 1 vs 3: Object 1 slows down while Object 3 remains constant.

So now my previous calculations are not correct. How do I avoid something like this situation? With a large set of units in a close area, this looks to be very difficult to solve. Though, I suppose if the objects are not moving very fast then the amount of collisions are very low.

I have some other cases, but I will post those up after we talk about this one Smiley

Offline JAW

Senior Devvie

Medals: 2

« Reply #4 - Posted 2007-05-25 13:07:53 »

You can use osbtacle avoidance when: maps are open and obstacles are small and have no dead ends. You can then just got direct path to target and avoid anything you encounter along the way.

When you have open areas connected by small portals, find your way from portal to portal.

But on complex terrain, you'll need real pathfinding. As a rule of thumb, you need real pathfinding when the direct path can lead to dead ends and obstacles which you cant go around. Hell, I cant tell convex and concave correctly Smiley

Offline amazing

Junior Newbie

« Reply #5 - Posted 2007-07-12 02:11:21 »

OMG!!! I honestly cannot believe that no one has thought of something so simple as Graph Theory! has no one ever heard of this??!!!

If you havent, graph theory finds paths from one point to another based on things like whether or not you tank can get you point A to point B.  It then tells you the path length.  If you know the shortest path length and you can find other path lengths from other points to yet more points,  you can then compute the points the tank would need to go to in order to get to its final destination, point C.

i know my definition is slightly... vague... but look it up in greater detail online and you'll see the light!... hopefully... if you cant seem to find the light maybe ill post somthieng in great detail on how to path find.

if no one has thought of this previous to my post... i feel kinda let down at the world.  I mea really... how many people went to school for this kinda thing and here i am, solving things on my for people *suposedly* vastly my seniors.
Offline appel

JGO Wizard

Medals: 80
Projects: 4

I always win!

« Reply #6 - Posted 2007-07-12 14:01:17 »

Pathfinding is done with graphs in computer games. Nothing new mate!
Offline keldon85

Senior Devvie

Medals: 1

« Reply #7 - Posted 2007-07-12 16:01:04 »

This is more than just path finding. When you are dealing with a world that is constantly changing your approach is completely different than just trying to find a route as any route you find will change over time.

To approach such a problem as a swarm you must develop (a) swarm behaviour, (b) some form of anticipation system to second guess the likely movement of the swarm in general and (c) awareness of your position in a large crowd. Take for instance a funnel or a road junction, eventually some people will have to either slow down or stop to let others pass or you end up with a jam situation. We have all seen human beings create traffic jams in situations where common sense will tell you that actually stopping and letting other cars pass will make your journey faster.

Pages: [1]
  ignore  |  Print  

hadezbladez (2614 views)
2018-11-16 13:46:03

hadezbladez (940 views)
2018-11-16 13:41:33

hadezbladez (2567 views)
2018-11-16 13:35:35

hadezbladez (506 views)
2018-11-16 13:32:03

EgonOlsen (3711 views)
2018-06-10 19:43:48

EgonOlsen (4109 views)
2018-06-10 19:43:44

EgonOlsen (2470 views)
2018-06-10 19:43:20

DesertCoockie (3275 views)
2018-05-13 18:23:11

nelsongames (3366 views)
2018-04-24 18:15:36

nelsongames (4345 views)
2018-04-24 18:14:32
Java Gaming Resources
by philfrei
2019-05-14 16:15:13

Deployment and Packaging
by philfrei
2019-05-08 15:15:36

Deployment and Packaging
by philfrei
2019-05-08 15:13:34

Deployment and Packaging
by philfrei
2019-02-17 20:25:53

Deployment and Packaging
by mudlee
2018-08-22 18:09:50

Java Gaming Resources
by gouessej
2018-08-22 08:19:41

Deployment and Packaging
by gouessej
2018-08-22 08:04:08

Deployment and Packaging
by gouessej
2018-08-22 08:03:45 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‑
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!