Little mathematical/programming puzzle for you to solve

[InCreator]

I'll start with an image, since text will be messy...



Observe. Starting square is (x,y). I drew only a quarter of the "circle" to keep it simple.

On 8 directions, there's a clearly visible pattern. We add or subtract an incremental number to X and Y, forming a cross similar to the one on UK's flag.

Now, in a code - as I drew, we would need 8 lines to define the possible variants of square position and a variable for increment. This would be simple for any amateur programmer. It would cover all squares I drew position values to -- to infinity. That's the amount of problem I *can* solve...

But as spiral gets bigger than 9 squares, there will be gaps... and uncovered variants will be infitite (squares marked with asterisk) so manual checking would be wild and some smart snippet of code should do it.

What I want is some kind of pseudocode to do grid checks in a perfect spiral. Code that spirals outwards and checks EVERY square, not only in 8 directions.

By pseudocode I mean anything readable to AGSer/C/delphi/basic programmer. All of those languages are similar and I guess that it's behind some simple (and similar in all languages) -  trigonometric function, but cosines and tangents at school managed to avoid me like cats do water.

It's not AGS-related really, I'm trying out my hand on real-time strategy game and this is last bit of pathfinding I cannot figure out.

EDIT: Fixed error.

Also, thinking about it, i've heard about crazy mathematical term "modulo"... could this be applied here? how?

[LUniqueDan]

Interesting problem InCreator!
(allas, a small error on {x-2,y}

I'll get you back if I find something (And before the morning crew shows up with the solution)

[Mr Jake]

I can't be bothered to write the absolute specifics, but I'd probably do it similar to how I was taught Flood Fill works.

The general idea is:

Each tile should have a flag of some sort, somewhere, which marks them as "visited"

Store each tile in a multidimensional array (indexed x, y).

Starting at the central index, check it and then step right (x+1,y).  Remember the direction we have stepped.
Depending which direction we have stepped, check if the tile (above, below, left, right) has been flagged as checked (ABOVE for right, BELOW for left, LEFT for up, RIGHT for down).

If the tile we check _hasn't_ been visited then we need to visit it and repeat (again, remembering the direction we stepped), owise keep going in the same direction and repeat.

Yeah, its not pseudocode, but hopefully its a pretty decent outline and maybe what you are looking for.

[Radiant]

Okay.

Code: ags

enum direction = { right, up, left, down };
dx [] = { 1, 0, -1, 0 };
dy [] = { 0, -1, 0, 1 };

int x=0. y=0, len = 1, dir = right, step = 0;

while (1) {
  do_something_at_square (x, y);

  x += dx[dir]; y += dy[dir];
  step ++;
  if (step >= (len + 1) / 2) {
    step = 0;
    len ++;
    dir = (dir + 1) % 4;
  }
}

How does this work? First we take one step right, then we rotate and take one step up and rotate again. Now we take two steps left, rotate, and two steps down, rotate. Now we  take three steps right, rotate, three steps up. See the pattern here?

(note that this pseudo-code never ends, looping over an infinitely large spiral; it needs a boundary condition, of course).

[The Bedminster Incident]

Same idea, but a different coding style:

Code: ags

int d[] = { 1, 0, -1, 0 };
int x = startX, y = startY, len = 2, dir = 0; //startX and startY are the respective coords to start with.

while (boundary_check()) {
  for (int i = 0; i < len; i++) {
    do_something_at_square(x, y);
    x += d[dir];
    y += d[(dir + 1) & 3];
  }

  dir = (dir + 1) & 3;

  for (int i = 0; i < len; i++) {
    do_something_at_square(x, y);
    x += d[dir];
    y += d[(dir + 1) & 3];
  }

  len++;
}

The "& 3" basically works like "% 4," but is handled quicker by the CPU, as it just binary-ANDs with "11." Also, we don't need two arrays, as the circles are basically the same, but biased by 1. If your boundary check is just checking the length, you could init len to 1, remove the len++ line and use something like "while (len++ < max_length) {."

I suppose Radiant's code might still be a tad more efficient, though.
/tbi

[Khris]

Here's a solution using a single function:

Code: ags

function spiral(int x, int y, int ul) {
  int ax = 1, ay, c = 1, i, j;
  while (c<ul) {
    j = 0;
    while (j<2) {
      i = 0;
      while (i<c) {
        x+=ax; y+=ay;
        do(x, y);
        i++;
      }
      if (j==0) { ay=-ax; ax=0; }
      else { ax=ay; ay=0; }
      j++;
    }
    c++;
    Wait(5);
  }
}

[InCreator]

Aha!

Radiant, you quite simply pointed out what I need -- to check z amount of squares, adding 90 degrees to move direction, repeat, and then add +1 to the z and restart loop. I didn't notice such logic in this.

Yeah, that's an usable pattern and loop.  I can do boundary checks simply by putting upper limit to z so pathfinding wouldn't last forever and would fail if no free square was found after z reached some number.


Thanks! Others too, since after adapting, I can chop something together from this code.

[MrColossal]

Hey can you explain or link to an explanation of how this works for pathfinding?

When I was messing around with pathfinding I tried flood fill and this seems similar only instead of radiating out you just spiral out. But since there is only one point that is searching for a path, what happens when it hits a wall? Does it just pathfinding into and through collision and leave that data out?

[InCreator]

Well, it's used for 2 things: grouped unit movement and position when unit is built from a house.

Let's say I have 9 units grouped. I click on a square. Now, one unit can occupy this square. But what should others do?

Of course I want other units to go as near as possible also.  Logic says that using infinite (or rather really big) spiral would generate closest possible waypoints. And infinite because it doesn't care how much units are selected. it will go spiraling outwards until free square is found for every unit.

For speed purposes, I will either limit maximum amount of units grouped or simply let game fail pathfinding if spiral gets too big, otherwise pathfinding would simply get super slow for masses.

As for collisions, I haven't given it much thought yet but yes, I'll probably simply mark everything unwalkable as not-free-square and continue spiral checking until squares are found.

Also, spiral motion is what you see in old RTS games where units are created from building: they occupy squares around building in same way. That's what led me to spiral.

I'm trying to get atleast something on the level of warcraft 1/Dune 2 etc. So I try to keep things rather simple - spiral doesn't let me use unit formations, for example. But that would be way above my skills too.

...
In the past I used to count number of grouped units, taking a square root of their amount and building a square-shaped grid of waypoints, but spiral feels much more reasonable here.

EDIT: ...and after lots of coding and fixing, problem is solved! Thanks again everyone, especially Radiant for figuring out simple logic behind spiral. Following is already computer-generated image using the logic supplied above, nothing was hand-drawn, a spiral of 150 steps, number shows repetition amount in one direction.

[MrColossal]

Ah ok, so this would be used for grouping them together at the end of their pathfinding not for finding the path from one end of the map to the other? That's neat.

Wouldn't you not want to iterate through collision because it's just wasted work?

[InCreator]

Yes... well, spiral decides to which square should unit *start* looking the path to. Pathfinding itself is grid-based A* which works quite well.

Wouldn't you not want to iterate through collision because it's just wasted work?

I have no clue what you just asked  

Spiral IS for figuring out which nearby squares are collision-free when middle (the clicked onto) one isn't. Also, when there's a group, every unit reserves itself a square (even before moving) and every unit after first one uses spiral to get theirs.

Now, buggy and stupid part in this is that other units cannot occupy or pass those squares even when unit meant to stop there is still half a map away... but I'm looking solution for this one also.

Maybe program different logic for pathfinding to define "pass while moving" and "stop moving on" squares?  or skip reserving and do spiral checks more often.

I'm still not sure if programming is fun or frustrating. Feels both... 

[Tuomas]

...nerds  :

[MrColossal]

Wouldn't you not want to iterate through collision because it's just wasted work?

I have no clue what you just asked

Hmm what I mean is

000000XX
0000XXXX
X00XXXXX
XX0XXXXX
XX00XXXX

If O's are land and X's are collision and your starting point for the spiral is the bold O, you look right first and then up and those are 2 collision areas so you've just wasted time searching there. Now you'll keep looking and eventually you'll be searching more collision areas than walkable terrain.

Make sense? It might not be a problem at all, just curious.

If this doesn't make sense either I'll just drop it.

[InCreator]

Well, to *know* that there's a collision there I have to *check* it, right...?

So -- erm... it's collision-check routine this way or another. If i'd let game magically know where collision areas are, I wouldn't need spiral checking at all?

[MrColossal]

I guess I keep thinking about the flood fill routine I wrote many moons ago in the fact that it wouldn't check a point surrounded by collision because it couldn't get to it.

Anyway thanks for clarifying!