16
\$\begingroup\$

There's some issues that I've come across in my Perlin noise-based game. Take a look at the attached screenshot below.

enter image description here

The white areas you see are walls, and the black areas are walkable. The triangle in the middle is the player.

I've implemented physics in this game by drawing it onto a texture (white or black pixels), and then getting that from the CPU.

However, now I stand with a different problem at hand. I want units (or creeps, whatever you call them) to spawn constantly, at the edge of the screen. The point here is that in the final game, there will be a "fog of war" that doesn't allow the player to see that far anyway.

I figured that I could just scan the pixels at the edge of the screen and see if their physics texture is black, and then spawn stuff randomly there. However, if you take a second look at the screenshot, there is (in the upper-left corner) an example of where I wouldn't want the creeps to spawn (since they wouldn't be able to reach the player from there).

Is it possible to somehow have the GPU determine these spawn-spots for me, or some different way? I thought about making vectors between the proposed point at the edge of the screen and the player, and then following it every 10 voxels, and see if a wall collides, before spawning a unit there.

However, the above proposed solution may be too CPU intensive.

Any suggestions on this matter?

Note 1 For the units spawned, I do not want to be using any form of pathfinding to avoid wall collisions as these units run towards the player. Therefore, the units must spawn at the edge of the screen, at a location where walking in a straight line towards the player would not collide with any walls.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Does the map move around with the player, or does the player move around in the map? That is, will the map be changing? If not, I'd suggest filling in all the non-reachable points at generation, so that you don't need to worry about them. \$\endgroup\$
    – dlras2
    Sep 11, 2011 at 16:28
  • \$\begingroup\$ If the player is moving, the units will need a path finding method. If you want concave areas you will have this problem and you have to provide a solution for the moving unit trying to reach a moving player... aka path finding. \$\endgroup\$
    – Blau
    Sep 12, 2011 at 8:25
  • 1
    \$\begingroup\$ Or, to put Blau's comment another way: Your question has provably no valid answer (aside from the trivial case of a map with no wall tiles/pixels at all) if the player can move. It still requires that you define what you mean with "straight line" to have an answer if the player is stationary. \$\endgroup\$ Sep 13, 2011 at 14:59

7 Answers 7

3
\$\begingroup\$

There's a pretty useful algorithm for this job, much more efficient than the flood algorithm in this situation (its complexity is runtime is proportional to the boundary size rather than the flooded area): it's the marching squares algorithm. The concept is simple: start off the players location (screen midpoint), choose a direction and walk until you find a wall. When you collide with the wall, you start the algorithm: you choose an orientation (up or down) and start marching over the boundary of this area, highlighting the pixels. This give you the inner boundary for the allowed area. Afterwards, you simply check whether the candidate points for spawning units lie on this boundary.

This is the principle you should follow for running the boundary:

http://en.wikipedia.org/wiki/File:Marchsquares.png (meh I can't post pics yet)

Wikipedia description (although it has alot more complexity because it's used with other applications in mind):

http://en.wikipedia.org/wiki/Marching_squares

\$\endgroup\$
10
\$\begingroup\$

Make a flood fill from the player's position; every area "flooded" is then a valid play area, and all others are walls.

EDIT: As to the "reachable in a straight line" additional requirement, keep in mind that in a discrete space, you have to define this a bit further. For example, all of the paths above could be a valid "straight line" in such an environment, and I've seen all of them used in a game at some point or another:

"straight line" variants

In particular, most of those aren't commutative - which means just because you can reach B from A in a "straight line" doesn't mean you can also reach A from B; neither is the opposite necessarily true.

In addition, there's the question on how do you handle diagonal movement if one or both of the "side" points is blocking.

\$\endgroup\$
8
  • \$\begingroup\$ Can this be implemented entirely in HLSL? \$\endgroup\$ Sep 10, 2011 at 20:24
  • \$\begingroup\$ @Mathias Lykkegaard Lorenzen: Yes, in doubt by doing each step of the algorithm as a pixel shader and rendering between two texture targets for example, but ... why? You'll likely need the information from the algorithm on the CPU anyway, for path finding at the very least. \$\endgroup\$ Sep 10, 2011 at 20:39
  • 1
    \$\begingroup\$ @Mathias Lykkegaard Lorenzen: That's slightly different from what you asked for, though. In this case: How do you define a "straight line", given your discrete space partitioning schema? \$\endgroup\$ Sep 10, 2011 at 20:56
  • 2
    \$\begingroup\$ even if you don't want to use pathfinding, asking cpu to do the floodfill job is possible, remember you only need to call floodfill once and then you will have a texture of 3 colors defining wall, free spaces, and spawnable spaces. for 4096x4096 texture it would take less than a sec for cpu to complete floodfill job. \$\endgroup\$
    – Ali1S232
    Sep 10, 2011 at 21:20
  • 1
    \$\begingroup\$ The point is that you only have to run this flood fill once, and even if your terrain changes while gameplay you only have to update the sections that are affected and have floodfill run through them which is hellishly fast. \$\endgroup\$
    – TravisG
    Sep 11, 2011 at 13:34
1
\$\begingroup\$

How about just letting the spawns happen? I don't see any particular problem in that.

\$\endgroup\$
6
  • \$\begingroup\$ And what if they spawn behind a wall? How would you make them reach the player? \$\endgroup\$ Sep 10, 2011 at 20:45
  • 1
    \$\begingroup\$ it could be a problem if the game has a scenario to kill all enemies, and it spawns 50 enemies, but a few were spawned behind the wall. The player wouldn't be able to kill the enemies and the scenario wouldn't finish. \$\endgroup\$
    – Lie Ryan
    Sep 10, 2011 at 22:35
  • 1
    \$\begingroup\$ Other units still may not be able to reach the player depending on how the player moves after they are spawned, you will have to unspawn some units in either case. \$\endgroup\$ Sep 11, 2011 at 6:06
  • \$\begingroup\$ the fog of war will cover the crappy spawns \$\endgroup\$
    – KRB
    Sep 11, 2011 at 7:06
  • 1
    \$\begingroup\$ That won't work anyway when the player moves. \$\endgroup\$ Sep 11, 2011 at 12:24
1
\$\begingroup\$

if it's important for you to only mark points with a valid straight line to the player you can use an algorithm like the following (it's a c++ code), it consumes more than than normal floodfill. there may be some minor bugs (I'll be glad if anyone corrects them) since i didn't test the code myself but you'll get the idea.

void straightlineFill(Point startPoint, Texture target)
{
    queue<Point> pointQueue;
    for (int dx = -1;dx <=1;dx ++)
            for(int dy = -1;dy <=1;dy++)
                if(dx != 0 && dy != 0)
                    pointQueue.push(point(startPoint.x + dx, startPoint.y + dy));
    while (!pointQueue.empty())
    {
        point front = pointQueue.front();
        pointQueue.pop();
        if (target.pixelAt(front) == COLOR_SPAWNABLE||
            target.pixelAt(front) == COLOR_WALL||
            target.pixelAt(front) == COLOR_NOT_SPAWNABLE)
                continue;
        taraget.setPixelAt(front, colorFilled); 
        for (int dx = -1;dx <=1;dx ++)
            for(int dy = -1;dy <=1;dy++)
                if(dx != 0 && dy != 0)
                    pointQueue.push(point(front.x + dx, front.y + dy));
        // up until now was the normal floodfill code
        // and here is the part that will do the real straight line checking

        // lineDX & lineDY will keep how much the line we are checking is skewed
        int lineDX = front.x - startPoint.x;
        int lineDY = front.y - startPoint.y;

        // step will show us how much we have to travel to reach each point of line
        point step;
        if (abs(lineDX) < abs(lineDY))
        {
            if (lineDX < 0)
                step = point(-1,0);
            if (lineDX == 0)
                if (lineDY < 0)
                    step = point(0,-1);
                else
                    step = point(0,1);
            if (lineDX > 0)
                step = point(1,0);
        }

        if (abs(lineDX) < abs(lineDY))
        {
            if (lineDY < 0)
                step = point(0,-1);
            if (lineDY == 0)
                if (lineDX < 0)
                    step = point(-1,0);
                else
                    step = point(1,0);
            if (lineDY > 0)
                step = point(0,1);
        }

        // moved will keep how much we have traveled so far, it's just some value that will speed up calculations and doesn't have any mathematical value
        point moved = 0;

        // spawnable will keep if the current pixel is a valid spawnpaint

        bool spawnable = true;

        // now we will travel on the straight line from player position to the edges of the map and check if whole line is valid spawn points or not.

        while (target.isInside(front))
        {
            front = front + step;
            moved = moved + point(step.x * lineDX, step.y * lineDY);
            if (step.x != 0 && moved.x < moved.y)
            {
                moved.x = moved.x - lineDY * sign(lineDY);
                front.y = front.y + sign(lineDY);
            }
            if (step.y != 0 && moved.y < moved.x)
            {
                moved.y = moved.y - lineDX * sign(lineDX);
                front.x = front.x + sign(lineDX);
            }

            if (target.getPixelAt(front) == COLOR_WALL)
                spawnable = false;

            if (spawnable)
            {
                target.setPixelAt(front,COLOR_SPAWNABLE);
                for (int dx = -1;dx <=1;dx ++)
                    for(int dy = -1;dy <=1;dy++)
                        if(dx != 0 && dy != 0)
                            pointQueue.push(point(front.x + dx, front.y + dy));             
            }
            else
            {
                target.setPixelAt(front,COLOR_NOT_SPAWNABLE);
            }
        }
    }
}
\$\endgroup\$
0
1
\$\begingroup\$

You can fill the map with colors that represents convex areas..., this way you can spawn your unit if lies in the same area. Or you can search easier for reachable areas.

This is static data so you can precalc it.

you had to fill the image finding points where there is a change from convave to convex, visually it's seems easy to find, you have two situations:

  1. Horizontal: Where orange to blue changes.
  2. Vertical: Where red changes ot green and orange.

enter image description here

\$\endgroup\$
5
  • \$\begingroup\$ This doesn't work. Look at the bottom right, specifically the blob in the red area. It's entirely convex so there's no change to cause another color to be used but clearly no straight line exists from the bottom of the red on the right edge to the rightmost part of the red on the bottom edge. \$\endgroup\$ Sep 11, 2011 at 21:36
  • \$\begingroup\$ @Loren Pechtel this is hand made, you are right, there is an error there, it's my fault , but you can realize that is the same situation that the orange to blue transition. \$\endgroup\$
    – Blau
    Sep 11, 2011 at 23:31
  • \$\begingroup\$ @Loren Pechtel, remind that the objetive is avoid to spawn in areas like yellow. This method ensure that if you release an enemy in the same area that contains the player, this is reachable. Of course, it may be tricky to implement, but the idea is valid. \$\endgroup\$
    – Blau
    Sep 12, 2011 at 0:39
  • \$\begingroup\$ Your revision doesn't help. Two points on a convex curve will never have a legal straight line between them, period. More divisions won't help. \$\endgroup\$ Sep 12, 2011 at 17:40
  • \$\begingroup\$ please check the definition of convex referring to areas or set of points... en.wikipedia.org/wiki/Convex \$\endgroup\$
    – Blau
    Sep 12, 2011 at 18:21
1
\$\begingroup\$

Here is something that I actually used in my own game (2d simplex noise generated world, almost exactly like yours)- Rays. Start at the player, determine a orientation (random if you want), and go along that line until you hit something (edge of screen OR asteroid). If you hit the edge of the screen (and not a asteroid/white blob), then you know there is a straight, open line from the edge of the screen to the player. Then spawn a monster at the point you hit. If you hit an asteroid, re-do the test.

\$\endgroup\$
0
\$\begingroup\$

Another (non-GPU) solution you can use is path-finding. Before drawing the map, path-find from each potential spawn-point at each edge of the map and see if there's a path to the center. A* path-finding is pretty OK on cost/performance, but you can do this before the game starts if that's an issue.

Any spawn point that doesn't have a path can be put on an exclusion list; or vice-versa (any point with a path can be put on an inclusion list).

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .