A star algorithm, unusual behaviour

Question

I am working on programming A star algorithm for a computer game project for college. I will be quite honest i am concerned that as soon as i mention college i will have any responders going west, i also admit the size of the 2d array of Nodes i am using to work with is very big, with a width = 800 & height = 800 I have managed the get it for the best part working. However i have come to an interesting bug

if (!diagonalMovementAllowed) {
                            if ((x != 0) && (y != 0)) {
                                continue;
                            }
                        }

without the below code, i can find the goal from any coordinate as long as it is within bounds of the 2d array, however if i do use the above code, the algorithn doesn't seem to be able to reach goal, if the start or goal is of somewhat cosiderable distance, for example

if goal x = 700 & y = 700 and if start x = 0 & y = 700, no problem

however if goal x = 700 & goal y = 700 and if start x = 690 & y = 720 it seems that it cannot find a path

my question is can an arrayList (open or closedList) reach a point where it simply cannot find a goal and has reached a size thats so incredibly high that it simply quits and is there a way to identify whats causing this, without looping through each x and y coordinate using debugger?

i do have a feeling this is rather vague question, but i am hoping that i can get a general answer as i don't feel many people would be too inclined to walk me through an entire explanation, especially since i did mention its a project and my lecturers seem to be aware of anything and everything. I hope that i can get some advice and answers and thanks in advance.

edit: To answer the 2 questions below (thanks for quick response)

for(int x = -1; x < 2; x++){
     for(int y = -1; y < 2; y++){


    if (!diagonalMovementAllowed) {
          if ((x != 0) && (y != 0)) {
              continue;
          }
        }
int neighborX = x + current.x;
int neighborY = y + current.y;
      }
    }

the above code is part of it, i obviously don't want to post it all as my lecturer will probably shoot me (or fail) for getting too much help but to explain what the above is doing

while the openList is not empty, loop through the neighbors of x and y x = x -1 or x = x +1 y = y -1 or y = y +1

0,0 0,1 0,2 1,0 1,1 1,2 2,0 2,1 2,2 if you are at 1,1 (start) and if you don't want diagonal movement then the following should be allowed (0,0) (2,0) (2,2) or (0,2) this is achieved by stopping both x and y from not being equal to 0 for example

neighborX = x + current.x
  1       = 0 + 1
 neighborY = y + current.y
   2         1 + 1
(1,2)

neighborX = x + current.x
  1       = 0 + 1
 neighborY = y + current.y
  0        -1 + 1
(1,0)

neighborX = x + current.x
  2       = 1 + 1
 neighborY = y + current.y
  0        -1 + 1
(2,0)

neighborX = x + current.x
  0       = -1 + 1
 neighborY = y + current.y
  0        -1 + 1
(0,0)

Ted Hopp Ted Hopp · Accepted Answer · 2012-11-21T00:54:00

I'm assuming that your code snippet is part of the successor generation logic. Unfortunately, I don't think the logic is right:

if (!diagonalMovementAllowed) {
    if ((x != 0) && (y != 0)) {
        continue;
    }
}

When diagonal movement is not allowed, this will prevent any successors being generated from interior positions (positions that are not in the x==0 column or y==0 row).

If my assumptions about your code are right, this is why no solutions can be found when the start position is something like x = 690 & y = 720—the start position has no successors!

A star algorithm, unusual behaviour

3 Answers