Android Question [solved]How can I get the coordinates of the path in a loop?

[Mark Read]

Consider the picture below. I have the coordinates of the black center pixel. I need a loop to get the coordinates of the white path around the center. The loop must take into account the varying size of each picture. For instance from left to right, a variable (lets say radius) would have the value 1, 2 and 3 respectively.

This is part of my pathfinding app. I take the coordinates of each "pixel" on the white path and add a weighting factor to it. This is the distance as the crow flies. For example in the right picture, the red square would be int(sqrt(3^2+3^2)*10)=42

Even better would be if I could use a circle instead of a square!
Thanks for any help.

 

[James Chamblin]

For a circle, it's easy. In pseudocode

'!Pseudocode!
For Angle = -180 to 180 Step Size
   X = CenterX + cosine(Angle) * Radius
   Y = CenterY + sine(Angle) * Radius
   Plot X,Y
Next

Size will need to be adjusted so it is small enough to plot all pixels, but large enough so the plot won't be slowed down.

A square takes a few extra steps.

'!Pseudocode!
'Plot top
Y = CenterY - Radius
For x = CenterX - Radius To CenterX + Radius
   Plot X,Y
Next
'Plot Right
X = CenterX + Radius
For Y = CenterY - Radius to CenterY + Radius
   Plot X,Y
Next
'Plot Bottom
Y = CenterY + Radius
For X = CenterX + Radius to CenterX - Radius Step -1
   Plot X,Y
Next
'Plot Left
X = CenterX - Radius
For Y = CenterY + Radius to CenterY - Radius Step -1
   Plot X,Y
Next

This example will plot around the square, first to the right, then down the right side, then to the left, then up the left side. If following path of movement doesn't matter, it can be simplified to

'!Pseudocode!
For i = -Radius to Radius
   Plot CenterX + i, CenterY - Radius 'Top
   Plot CenterX + i, CenterY + Radius 'Bottom
   Plot CenterX - Radius, CenterY + i 'Left
   Plot CenterX + Radius, CenterY - i 'Right
Next

 

[Mark Read]

This is great James, thanks.

The last code looks good. It would be easy to read. My next problem is I have to modify the code to this:

'!Pseudocode!
For i = -Radius to Radius
   x=CenterX + i: y= CenterY - Radius 'Top
   AddPoint(x,y)
   x=CenterX + i: y= CenterY + Radius 'Bottom
   AddPoint(x,y)
   x=CenterX - Radius: y= CenterY + i 'Left
   AddPoint(x,y)
   x=CenterX + Radius: y= CenterY - i 'Right
   AddPoint(x,y)
Next

The points are added to array and then checked to see if they are on the required path. If so, they are moved to a second array. At present I am using radius=1 and it is working but I run the sub nearly 1000 times to check 8 squares. If I switch to radius=2 then I run fewer times but have 14 squares to test. The effect is about the same I think. Bearing in mind that my tablet has a resolution of roughly 1000x800, I need a lot of points for a path. How could I increase speed? The code is in an activity. Would a class or thread but quicker?

If interested, this is a modified "A star" algorithm as detailed here: http://www.policyalmanac.org/games/aStarTutorial.htm

I have the app working but I can watch it build the path (its cool!).

 

[James Chamblin]

You could break down the checks over multiple frames. Instead of doing 1000 checks before moving the character, you can do 100. Then move the character in the direction of the best guess. While moving the character to the new location, you do the next 100 checks and adjust the character if needed for the new information. If it takes the character 1 second to move a full square away and your game loop is running 30 fps, you will have the correct path calculated by the time the character is 1/3 of the way to it's first square, masking any corrections you had to make along the way. And of course, you now have an additional 20 frames left to calculate the next position, assuming that the destination is also moving, such as when a monster is chasing the player; otherwise no more checks are necessary.