CODEWITHSUNDEEP
java2d
machinateur
machinateur

Reputation: 500

Calculate 2d coordinates in radius (for a tile based game)

I've searched for a while and could not manage to find any satisfying answer.

Currently I have a list of tiles (an int array representing the tile id), the width and height (in tiles). When I render it, all tiles are placed correctly, etc. But my real problem is that I can't figure out an algorithm to calculate the tiles inside a given radius (relative to another tile) from the inside out. I plan to use this for lighting calculation. That's why I need to calculate from the inside out (for the gradient). I can't use static calculations using + and - on x and y because I plan to have variable radius sizes. Does anyone know a good way to do this?

EDIT: By "from the inside out" I mean the way the lighting is layed out, near the light source the lighting should be more intense than far from it. With the following ASCII thing I intend to show this visually:

0  0  0  0  0  0  0
0  0 --------- 0  0
0  |  *  +  *  |  0
0  |  +  x  +  |  0
0  |  *  +  *  |  0
0  0 --------- 0  0
0  0  0  0  0  0  0

Thanks in advance :)

Upvotes: 0

Views: 801

Answers (1)

Marco13
Marco13

Reputation: 54639

There certainly are many different options concerning the details of how this could be implemented. You did not tell exactly how you represent your "tiles" (regarding interfaces, for example). But here is one approach, maybe it already helps:

The idea is to store the coordinates of the tiles as a list of Point objects. (Converting these points into 1D indices is possible, but should be fairly independent of the actual question).

These points are computed by walking along the "edges" of the area in question:

  • Starting at the lower right corner, going upwards (dx=0, dy=-1)
  • Starting at the upper right corner, going left (dx=-1, dy=0)
  • Starting at the upper left corner, going down (dx=0, dy=1)
  • Starting at the lower left corner, going right (dx=1, dy=0)

All these points are put into a list, which afterwards contains all points that have a certain Manhattan Distance to the center point, in counterclockwise order.

import java.awt.Point;
import java.util.ArrayList;
import java.util.List;

public class TileDistances
{
    public static void main(String[] args)
    {
        int sizeX = 11;
        int sizeY = 11;
        int centerX = 5;
        int centerY = 5;

        for (int radius=1; radius<5; radius++)
        {
            System.out.println(
                "Radius "+radius+" around "+centerX+","+centerY);
            List<Point> points = coordinates(centerX, centerY, radius);
            char c = (char)('0'+radius);
            System.out.println(createString(points, sizeX, sizeY, c));
        }
    }

    private static String createString(
        List<Point> points, int sizeX, int sizeY, char c)
    {
        StringBuffer sb = new StringBuffer();
        for (int y=0; y<sizeY; y++)
        {
            for (int x=0; x<sizeX; x++)
            {
                Point p = new Point(x,y);
                if (points.contains(p))
                {
                    sb.append(c);
                }
                else
                {
                    sb.append(".");
                }
            }
            sb.append("\n");
        }
        return sb.toString();
    }

    private static List<Point> coordinates(
        int cx, int cy, int r)
    {
        List<Point> coordinates = new ArrayList<Point>();
        int steps = r + r;
        addAll(cx + r, cy + r,  0, -1, steps, coordinates);
        addAll(cx + r, cy - r, -1,  0, steps, coordinates);
        addAll(cx - r, cy - r,  0,  1, steps, coordinates);
        addAll(cx - r, cy + r,  1,  0, steps, coordinates);
        return coordinates;
    }

    private static void addAll(
        int x0, int y0, int dx, int dy, int steps,
        List<Point> coordinates)
    {
        int x = x0;
        int y = y0;
        for (int i=0; i<steps; i++)
        {
            coordinates.add(new Point(x,y));
            x += dx;
            y += dy;
        }
    }
}

In this example, radiuses 1 to 4 will be printed, for example:

Radius 3 around 5,5
...........
...........
..3333333..
..3.....3..
..3.....3..
..3.....3..
..3.....3..
..3.....3..
..3333333..
...........
...........

(There may be more efficient and/or more elegant solutions for this, depending on how exactly the tiles are represented, but I think that this one is easy to understand and generically applicable, because it just delivers a set of coordinates, and does not make assumptions about the underlying data structures).

Upvotes: 1

Related Questions