Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (784) Games in Android Showcase (234) games submitted by our members Games in WIP (858) 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
 Detect "going in circles" i 2D grid.  (Read 6245 times) 0 Members and 1 Guest are viewing this topic.
jompe71

Junior Newbie

Java games rock!

 « Posted 2006-02-17 14:13:56 »

I have a 2D grid where the path an object moves through the grid is determined by a loop.
Every loop cycle i calculate the next step based upon certail criterias and add the path (grid coords) to a list.

But in this loop i need to detect if the object is going in circles ( an popentially avoid an eternity loop ).
As I figure it this is "only" to discover if the last coordinate plus the one I'm about to add already exists after each other in the path list ?!?

But this seems as I on EVERY calculated new path coord have to go over the list from the beginning to check
for the coord combination and the list grows by every added coord making the operation slower over time.

Anyone know of any faster way to detect this circular movement?
ryanm

Senior Devvie

Projects: 1
Exp: 15 years

Used to be bleb

 « Reply #1 - Posted 2006-02-17 14:43:35 »

Instead of having each object having a complete record of it's movements, you could have each box in your grid keep a record of the last time the object visited, and to which neighbouring box it went next.

Then, instead of having to iterate through a complete record of movements so far to detect loops, the object simply asks the grid it's on "Have I been here before? Was I going in the same direction the last time I visited?" Hey presto, we've reduced the run time from O(n), for a path of n steps, to O(1). As a side bonus, the memory requirements become slightly smaller too.
jompe71

Junior Newbie

Java games rock!

 « Reply #2 - Posted 2006-02-17 15:13:40 »

I got your point, and it actually should work im my case if the code ( or actually my objects within the grid where prepared for it ).
Unfortunatly this is not the case. My grid is just a level map with only integer values. Of course this can be changed...

Never the less i think I need a list of directions the object went at a certain grid cordinate. There is always the possibility of going in an "eight" or even a more complex path, eventually turning up going into "where gone before".

My 2nd thought was to have the grid location as some sort of hashed map key, and the list of directions the object went as value.
At least i would know there to look on each turn in the loop. The list of alternative directions the object went will assumebly be quite small.

This will of course consume more memory and not as fast as your solution,
but since I only will store a "couple of" integers, it'll be ok ?
 Games published by our own members! Check 'em out!
Riven

« JGO Overlord »

Medals: 1357
Projects: 4
Exp: 16 years

 « Reply #3 - Posted 2006-02-17 15:50:01 »

Check the cell you're standing on every N cycles. (N is fairly big)

 1  2  3  4  5  6 `float d = distance(currentPos, lastCheckedPos);float t = currentTime - lastTimeCheck;float speed = d / t;if(speed very very low)   // probably in a loop, or maybe returned from long trip :)`

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

Junior Newbie

Java games rock!

 « Reply #4 - Posted 2006-02-18 08:50:54 »

Actually it's not as if a player where standing on a coordinate in the grid.

I didn't make myself clear, but the case is I'm making a "path" in the grid by drawing a line from (X1,Y1) to (X2,Y2).
Based upon criterias and of course the level map the path can take a different turn on any coord.
The whole path is calculated at every frame and I need to detect if the path goes in circles or any more complex
path eventually turning into an eternity loop.

My grid is only built up by numeric values and holds no logic of its own.

ryanm

Senior Devvie

Projects: 1
Exp: 15 years

Used to be bleb

 « Reply #5 - Posted 2006-02-18 09:00:40 »

With regards to catching a figure-of-eight loop: storing only the last time the object was at each square will still detect the loop, it just won't be detected at the crossover point.
I've been trying hard to come up with some pathological edge case that wouldn't be caught by storing a single visit at each grid point, and the closest I've got is moving backwards and forwards in a straight line, and this is still caught at each end. NB: This assumes that the object will always move to another square, it can never stay in the same square.
jompe71

Junior Newbie

Java games rock!

 « Reply #6 - Posted 2006-02-18 10:03:00 »

Yep, seems as the logic will work perfectly. Didn't think of your point on the "figure-eight". I Assumed it would get lost at the cross over,
but your right it will be detected the next step after.
I'm gonna try on an implementation in my game, thx !
t_larkworthy

Senior Devvie

Medals: 1
Projects: 1

Google App Engine Rocks!

 « Reply #7 - Posted 2006-02-18 18:15:44 »

Oh wow, a geometric solution to a subset of halting problems!

Runesketch: an Online CCG built on Google App Engine where players draw their cards and trade. Fight, draw or trade yourself to success.
ryanm

Senior Devvie

Projects: 1
Exp: 15 years

Used to be bleb

 « Reply #8 - Posted 2006-02-18 20:35:43 »

I didn't do the Computability and Intractability module, so I wouldn't know about that. It smells like spacial indexing to me...
Pages: [1]
 ignore  |  Print

 hadezbladez (1621 views) 2018-11-16 13:46:03 hadezbladez (635 views) 2018-11-16 13:41:33 hadezbladez (1611 views) 2018-11-16 13:35:35 hadezbladez (329 views) 2018-11-16 13:32:03 EgonOlsen (2672 views) 2018-06-10 19:43:48 EgonOlsen (2937 views) 2018-06-10 19:43:44 EgonOlsen (1639 views) 2018-06-10 19:43:20 DesertCoockie (2347 views) 2018-05-13 18:23:11 nelsongames (2251 views) 2018-04-24 18:15:36 nelsongames (2946 views) 2018-04-24 18:14:32
 Deployment and Packagingby philfrei2019-02-17 20:25:53Deployment and Packagingby mudlee2018-08-22 18:09:50Java Gaming Resourcesby gouessej2018-08-22 08:19:41Deployment and Packagingby gouessej2018-08-22 08:04:08Deployment and Packagingby gouessej2018-08-22 08:03:45Deployment and Packagingby philfrei2018-08-20 02:33:38Deployment and Packagingby philfrei2018-08-20 02:29:55Deployment and Packagingby philfrei2018-08-19 23:56:20
 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