Detect "going in circles" i 2D grid.

Game Mechanics Artificial Intelligence
#1

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?

#2

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.

#3

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 ?

#4

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 :)
#5

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.

#6

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.

#7

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 !

#8

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

#9

I didn’t do the Computability and Intractability module, so I wouldn’t know about that. It smells like spacial indexing to me… :slight_smile: