1

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.

FillExample1:inprogress FillExample1: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.

enter image description here enter image description here

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?

2
  • Were any of the answers helpful? Do you plan to accept any?
    – afeldspar
    Commented Aug 6, 2014 at 12:12
  • Yes very helpful! Sorry been sidetracked by another project. Will review these again and accept -- thanks for help everyone :)
    – ImGreg
    Commented Aug 8, 2014 at 14:16

3 Answers 3

5

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!):

a border line which can approach within one cell of itself, and thus creates three sections in one move

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.

1
  • This is a very great and detailed answer! Never thought such a simple game would require this much of thinking. Commented Aug 2, 2014 at 21:02
4

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:
enter image description here

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:
enter image description here

14
  • What about the scenario where the line from the enemy crosses along your border (since border is a tile thick)? ie. in a square, the enemy line follows directly along the bottom edge of the square.
    – ImGreg
    Commented Aug 1, 2014 at 23:18
  • @ImGreg - Are you talking about if the enemy is right on the border? Commented Aug 1, 2014 at 23:21
  • No, but the horizontal line from the enemy (anywhere on map) crosses along the bottom edge of a square. Won't the result be odd/even based on the number of tiles that are along the bottom edge?
    – ImGreg
    Commented Aug 1, 2014 at 23:23
  • @ImGreg - I see what you're saying, but that seems a pretty simple case to handle. Say that the line goes from the enemy to the right screen on the 10th line down, and the border line coincides with that line for three cells - 8,10; 9,10; 10,10. Well, just check whether the lines that connect the "shared" segment to the rest of the border are on the same side or opposite sides of the shared segment. If the cells that connect vertically to the shared segment are 8,9 and 10,9 (both above the line) then it doesn't add one to the count. If the cells are 8,9 (above) and 10,11 (below) it does.
    – afeldspar
    Commented Aug 1, 2014 at 23:24
  • @ImGreg - Try out this example I made: jsfiddle.net/DerekL/8QBz6 because I don't quite get your question. Commented Aug 1, 2014 at 23:35
2

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.A region and an enemy

We can encode the region as a series of vectors that give it a clockwise orientation, like so: A region as a series of vectors. Now the path has an orientation.

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)...

Side determination process

...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!

3
  • Could you provide a basic example of this?
    – ImGreg
    Commented Aug 1, 2014 at 23:35
  • Shouldn't it be negative if it's outside? Commented Aug 2, 2014 at 21:49
  • Not the way I have it set up. If the arrows around the edge are going counter-clockwise instead, though, the outside is negative.
    – Ragaxus
    Commented Aug 3, 2014 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.