<p>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.</p>

<p>Since you are using a grid system this should be <s>easy</s> to implement (and very fast). This algorithm is called the <a href="https://en.wikipedia.org/wiki/Point_in_polygon#Ray_casting_algorithm" rel="nofollow noreferrer">Ray casting algorithm</a>.</p>

<p>Here's a simple example I created: <a href="http://jsfiddle.net/DerekL/8QBz6/" rel="nofollow noreferrer">http://jsfiddle.net/DerekL/8QBz6/</a> (can't deal with degenerate cases)</p>

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

<p>For example, you have this shape which you have determined:<br>
<img src="https://i.stack.imgur.com/UYywj.png" alt="enter image description here"></p>

<p><em>removed</em></p>

<hr>

<p>Guess <a href="http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html" rel="nofollow noreferrer">what I found</a>, (slightly modified)</p>

<pre><code>//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 &lt; wallList.length; j = i++) {
        if ( ((wallList[i][1]&gt;enemy[1]) ^ (wallList[j][1]&gt;enemy[1])) &amp;&amp;
            (enemy[0] &lt; (wallList[j][0]-wallList[i][0]) * (enemy[1]-wallList[i][1]) / (wallList[j][1]-wallList[i][1]) + wallList[i][0]) )
        c = !c;
    }
    return !!c;
}
</code></pre>

<p><a href="http://jsfiddle.net/DerekL/NvLcK/" rel="nofollow noreferrer">http://jsfiddle.net/DerekL/NvLcK/</a></p>

<p>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:</p>

<pre class="lang-none prettyprint-override"><code>     (X2 - X1)(Py - Y1)
Px &lt; ────────────────── + X1
          Y2 - Y1
</code></pre>

<p>which is derived by combining these two:</p>

<pre class="lang-none prettyprint-override"><code>Ray:
x(t) = Px + t, y(t) = Py, where t &gt; 0 (the ray goes to the right)

Edge:
x(u) = (X2 - X1)u + X1, y(u) = (Y2 - Y1)u + Y1, where 0 &lt;= u &lt;= 1
</code></pre>

<p>And the condition for y:</p>

<pre><code>(Y1 &gt; Py) ⊕ (Y2 &gt; Py)
</code></pre>

<p>which is equivalent to:</p>

<pre><code>(Y1 ≥ Py &gt; Y2) ∨ (Y2 ≥ Py &gt; Y1)
</code></pre>

<p>and yadi yadi yada some other interesting technical stuff.</p>

<p>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 <a href="http://arxiv.org/pdf/math/9410209.pdf" rel="nofollow noreferrer">this paper</a> (section 5.1).</p>

<p>Nevertheless, here's the result generated with the algorithm testing every coordinate:<br>
<img src="https://i.stack.imgur.com/mmkQO.png" alt="enter image description here"></p>
Tile Filling Algorithm for Game
<p><strong>Background:</strong></p>

<p>I am working on a tile-based game in Javascript where a character freely moves around the map (<strong>no diagonal</strong> - 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.</p>

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

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

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

<p><strong>My Question:</strong>
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)?<br>
IF YES, <strong>how do I determine where to start the algorithm from in a systematic way</strong> 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).  </p>

<p><strong>Picture Example 1 (pics explain better):</strong> </p>

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

<p><img src="https://i.stack.imgur.com/n4dxr.png" alt="FillExample1:inprogress">
<img src="https://i.stack.imgur.com/IJ9kz.png" alt="FillExample1:filled"></p>

<p><strong>Picture Example 2:</strong> </p>

<p>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.</p>

<p><img src="https://i.stack.imgur.com/LJ2Ew.png" alt="enter image description here">
<img src="https://i.stack.imgur.com/5rMk6.png" alt="enter image description here"></p>

<p><strong><em>Summary:</em></strong> 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?</p>