Tile Filling Algorithm for Game

Question

Background:

I am working on a tile-based game in Javascript where a character freely moves around the map (no diagonal - Left/Right/Up/Down) and fills in tiles as he moves around the map. There are three tile types -- tiles you've filled (blue), your current path (red), and empty ones (black). There are also enemies (stars) that move around the map as well, but only in empty areas. The objective is to fill as much of the map as possible.

Map is sized as roughly 40x40 tiles. There is a 1 tile thick border around the entire outside of the map that is already "filled" (blue).

I have established that a flood-fill algorithm will work for filling up areas of tiles when needed. However, my problem is as follows:

PROBLEM STATEMENT: I want to only fill a sectioned-off part of the map if there are no enemies in it.

My Question: I could run flood-fill algorithm and stop it if it reaches a tile occupied by an enemy -- however, is this the most efficient approach (for a real time game)?
IF YES, how do I determine where to start the algorithm from in a systematic way since there are multiple areas to check and the character doesn't have to move in a perfectly straight line (can zig-zag up/down/right/left, but can't move diagonally).

Picture Example 1 (pics explain better):

Note: red areas turn blue (filled) once you reach another filled area. In example below, there are no enemies in the contained area, so the area is filled.

Picture Example 2:

In this second example, there is an enemy within the contained area (and on the outside area - not shown) so nothing but the line is filled.

Summary: What is the best approach for doing this type of filling? Is flood fill the best choice for determining whether to fill or not -- 40x40 makes for a pretty large calculation. If yes, how do I determine what tile do I start with?

Answer 1

If you have the points of the border of your shape that lies on the same y as the enemy, then you can simply count the number of borders, starting from either left or right to the enemy. If it's odd then it's inside. If it's even then it's outside.

Since you are using a grid system this should be easy to implement (and very fast). This algorithm is called the Ray casting algorithm.

Here's a simple example I created: http://jsfiddle.net/DerekL/8QBz6/ (can't deal with degenerate cases)

function testInside(){
    var passedBorder = 0,
        passingBorder = false;
    for(var x = 0; x <= enemy[0]; x++){
        if(board[x][enemy[1]] === 1) passingBorder = true;
        else if(board[x][enemy[1]] === 0 && passingBorder){
            passingBorder = false;
            passedBorder++;
        }
    }
    return !!(passedBorder%2);
}

For example, you have this shape which you have determined:

removed

---

Guess what I found, (slightly modified)

//simple enough, it only needs the x,y of your testing point and the wall.
//no direction or anything else
function testInside3() {
    var i, j, c = 0;
    for (i = 0, j = wallList.length-1; i < wallList.length; j = i++) {
        if ( ((wallList[i][1]>enemy[1]) ^ (wallList[j][1]>enemy[1])) &&
            (enemy[0] < (wallList[j][0]-wallList[i][0]) * (enemy[1]-wallList[i][1]) / (wallList[j][1]-wallList[i][1]) + wallList[i][0]) )
        c = !c;
    }
    return !!c;
}

http://jsfiddle.net/DerekL/NvLcK/

This is using the same ray casting algorithm I mentioned, but this time the "ray" is now mathematical using the following inequality for x and a condition for y:

     (X2 - X1)(Py - Y1)
Px < ────────────────── + X1
          Y2 - Y1

which is derived by combining these two:

Ray:
x(t) = Px + t, y(t) = Py, where t > 0 (the ray goes to the right)

Edge:
x(u) = (X2 - X1)u + X1, y(u) = (Y2 - Y1)u + Y1, where 0 <= u <= 1

And the condition for y:

(Y1 > Py) ⊕ (Y2 > Py)

which is equivalent to:

(Y1 ≥ Py > Y2) ∨ (Y2 ≥ Py > Y1)

and yadi yadi yada some other interesting technical stuff.

Seems like this is the default algorithm in many native libraries. The method used to dealing with degenerate cases is called Simulation of Simplicity, described in this paper (section 5.1).

Nevertheless, here's the result generated with the algorithm testing every coordinate:

Answer 2

Let me suggest a different way of looking at your problem.

Going by the description of your game, it seems like the user's main, perhaps only, "verb" (in game design terms) is to draw a line that divides the open area of the field into two sections. If either of these two sections is free of enemies, that section gets filled in; if neither section is free of enemies, the line remains but both sections remain open. There are no other conditions determining whether a section gets filled or not, right?

So the most efficient way to solve this problem, I would think, is simply to draw a continuous line, which may make corners but only moves in horizontal or vertical directions, from one of your enemies to every other enemy in turn. We'll call this line the "probe line". From here on, we're using the approach of Derek's suggested "Ray casting algorithm": We look at the number of times the "probe line" crosses the "border line", and if the number of crossings is ever odd, it means you have at least one enemy on each side of the line, and there's no filling.

Note, though, that there's a difference between the two lines coinciding and the two lines crossing. Picture a probe line that goes from the coordinates (0,10) to (39,10) , and a border line that goes down from (5,0) to (5,10) and then goes right to (13,10). If it goes down from there towards (13,39), the two lines are crossing; if instead it goes upwards toward (13,0), they're not.

After a lot of thought, I strongly suggest that you store the "border line", and construct the "probe line", in terms of line segments - rather than trying to determine from which cells are filled which line segments created them. That will make it much harder than it has to be.

Finally, one odd game design note to be aware of: unless you constrict the user's control so that he cannot bring the border line back to within one cell of itself, then a single border line drawn by a user might end up sectioning off the field into more than two sections - there could be sections created by the border line looping right back on itself. If you allow that, it could very drastically complicate the calculation of where to fill. Check the following diagram I made via Derek's fiddle (thank you, Derek!):

As you can see, one border line has actually created three sections: one on the upper side of the line, one below the line, and one formed by the line itself. I'm still thinking about how that would affect things algorithmically, for that to be possible.

EDIT: With a) time to think about the above creation-of-multiple-sections-by-loops, and b) the Simulation of Simplicity resource brought up by Derek, I think I can outline the simplest and most efficient algorithm that you're likely to get.

There's one subproblem to it which I'll leave to you, and that is determining what your new sections are after the player's actions have drawn a new line. I leave that to you because it's one that would have had to be solved before a solution to your original problem (how to tell if there are enemies within those sections) could have been called.

The solution, presented here as pseudocode, assumes you have the border of each section stored as line segments between coordinates.

Create a list of the sections.
Create a list of the enemies.
Continue as long as neither list is empty:
  For each enemy in the enemy list:
  Designate "Point A" as the coordinates of the enemy, PLUS 0.5 to both x and y.
    For each section in the section list:
      Designate "Point B" as the upper-left-most coordinate, PLUS 0.5 to both x and y.
      Count how many of the section border segments cross a line between A and B.
      If the answer is even:  
        remove this section from the section list
        skip forward to the next enemy
If any sections remain in the list, they are free of enemies.  Fill them in.

The addition of the 0.5 to the coordinates of the "probe line" are thanks to Derek's SoS resource; they eliminate the difficult case where the lines coincide rather than simply crossing or not crossing.

Answer 3

If it's easy to determine where the borders of a region to possibly fill are, you can use the following approach:

1. Assign each edge a clockwise directionality. That is, construct a vector for each edge that starts on its corners and has a direction such that a clockwise path around the region is described by these vectors.
2. For each enemy:
   • Construct a vector starting from the enemy and ending on the closest edge. We'll call this an enemy_vector.
   • Calculate the cross product of the enemy_vector and the vector corresponding to the closest edge. The sign of the cross product will tell you whether the enemy is inside the region: if it's positive, the enemy is outside of it, and if it's negative it isn't!

EXAMPLE:

Suppose we have the following region and enemy to evaluate the inside-ness of.

We can encode the region as a series of vectors that give it a clockwise orientation, like so:

So how do we use that to determine the side of the region inhabited by the enemy? We draw a vector from it (which I've colored red) to the nearest edge (which I've colored green)...

...and take the cross product of the red vector and the green vector. Application of the right-hand rule tells us that (red) x (green) > 0, so the enemy must be outside the region!