Hi !
Featured games (85)
games approved by the League of Dukes
Games in Showcase (636)
Games in Android Showcase (178)
games submitted by our members
Games in WIP (687)
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 4376 times)
0 Members and 1 Guest are viewing this topic.
Offline 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 ).  Undecided
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?
Offline 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.
Offline 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!
Legends of Yore - The Casual Retro Roguelike
Offline Riven

« JGO Overlord »

Medals: 1068
Projects: 4
Exp: 16 years

Hand over your head.

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

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

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!
Offline 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.
Offline 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.
Offline 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 !
Offline 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.
Offline 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...  Smiley
Pages: [1]
  ignore  |  Print  
You cannot reply to this message, because it is very, very old.

Dwinin (72 views)
2015-11-07 13:29:08

Rems19 (81 views)
2015-10-31 01:36:56

Rems19 (74 views)
2015-10-31 01:32:37

williamwoles (107 views)
2015-10-23 10:42:59

williamwoles (93 views)
2015-10-23 10:42:45

Jervac_ (107 views)
2015-10-18 23:29:12

DarkCart (135 views)
2015-10-16 00:58:11

KaiHH (116 views)
2015-10-11 14:10:14

KaiHH (156 views)
2015-10-11 13:26:18

BurntPizza (171 views)
2015-10-08 03:11:46
Rendering resources
by Roquen
2015-11-13 14:37:59

Rendering resources
by Roquen
2015-11-13 14:36:58

Math: Resources
by Roquen
2015-10-22 07:46:10

Networking Resources
by Roquen
2015-10-16 07:12:30

Rendering resources
by Roquen
2015-10-15 07:40:48

Math: Inequality properties
by Roquen
2015-10-01 13:30:46

Math: Inequality properties
by Roquen
2015-09-30 16:06:05

HotSpot Options
by Roquen
2015-08-29 11:33:11 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!