Improving performance of click detection on a staggered column isometric grid
<p>I am working on an isometric game engine and have already created an algorithm for pixel perfect click detection. Visit the <a href="http://stalerz.herokuapp.com" rel="nofollow noreferrer">project</a> and notice that click detection is able to detect which edge of the tile was clicked. It is also checks the y-index to click the most upfront tile.</p>

<h1>An Explanation of my current algorithm:</h1>

<p>The isometric grid is made of tile images that are 100*65px.
<code>TileW=100, TileL=50, tileH=15</code></p>

<p><a href="https://i.stack.imgur.com/dq4RT.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/dq4RT.png" alt="Sizing of tile"></a></p>

<p>The map is represented by a three-dimensional array <code>map[z][y][x]</code>.</p>

<p>Tile center points <code>(x,y)</code> are calculated like so:</p>

<pre><code>//x, y, z are the position of the tile

if(y%2===0) { x-=-0.5; }    //To accommodate the offset found in even rows
this.centerX = (x*tileW) + (tileW/2);
this.centerY = (y*tileL) - y*((tileL)/2) + ((tileL)/2) + (tileH/2) - (z*tileH);
</code></pre>

<p><a href="https://i.stack.imgur.com/ckjOR.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/ckjOR.png" alt="Isometric grid"></a></p>

<p><strong>Prototype functions that determine if the mouse is within a given area on the tile:</strong></p>

<pre><code>Tile.prototype.allContainsMouse = function() {
    var dx = Math.abs(mouse.mapX-this.centerX),
        dy = Math.abs(mouse.mapY-this.centerY);

    if(dx&gt;(tileW/2)) {return false;}    //Refer to image
    return (dx/(tileW*0.5) + (dy/(tileL*0.5)) &lt; (1+tileHLRatio));
}
</code></pre>

<p><code>Tile.prototype.allContainsMouse()</code> returns true if mouse is within green. Red area is cropped out by checking if dx > half the tile's width</p>

<p><a href="https://i.stack.imgur.com/rzjHb.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/rzjHb.png" alt="Figure 1"></a></p>

<hr>

<pre><code>Tile.prototype.topContainsMouse = function() {
    var topFaceCenterY = this.centerY - (tileH/2);
    var dx = Math.abs(mouse.mapX-this.centerX),
        dy = Math.abs(mouse.mapY-topFaceCenterY);

    return ((dx/(tileW*0.5) + dy/(tileL*0.5) &lt;= 1));
};
</code></pre>

<p><a href="https://i.stack.imgur.com/vAyCt.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/vAyCt.png" alt="Returns true if mouse is on top face"></a></p>

<hr>

<pre><code>Tile.prototype.leftContainsMouse = function() {
    var dx = mouse.mapX-this.centerX;
    if(dx&lt;0) { return true; } else { return false; }
};
</code></pre>

<p>(If mouse is left of the center point)</p>

<hr>

<pre><code>Tile.prototype.rightContainsMouse = function() {
    var dx = mouse.mapX-this.centerX;
    if(dx&gt;0) { return true; } else { return false; }
};
</code></pre>

<p>(If mouse is right of the center point)</p>

<p><strong>Bringing all the methods together to work as one:</strong></p>

<ul>
<li>Loop Through the entire 3d map[z][y][x] array</li>
<li>if <code>allContainsMouse()</code> returns true, map[z][y][x] is the tile our mouse is on.</li>
<li>Add this tile to the array <code>tilesUnderneathMouse</code> array.</li>
<li><p>Loop through <code>tilesUnderneathMouse</code> array, and choose the tile with the highest <code>y</code>. It is the most upfront tile.</p>

<pre><code>if(allContainsMouse &amp;&amp; !topContainsMouse)
</code></pre></li>
</ul>

<p><a href="https://i.stack.imgur.com/kIqkg.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/kIqkg.png" alt="Bottom match"></a></p>

<ul>
<li><pre><code>if(allContainsMouse &amp;&amp; !topContainsMouse &amp;&amp; leftContainsMouse)
</code></pre></li>
</ul>

<p><a href="https://i.stack.imgur.com/aWfSG.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/aWfSG.png" alt="left match"></a></p>

<p>(Similar concept applies for right)</p>

<h1>Finally, my questions:</h1>

<p>#1 How would you accomplish this, such that it is more efficient(not looping through all tiles)(pesudo code accepted)</p>

<p>#2 If you are unable to answer #1, what suggestions do you have to improve the efficiency of my click detection (chunk loading has already been considered)</p>

<h1>What I've thought of:</h1>

<p>I originally tried to solve this problem by not using tile center points, rather converting the mouse(x,y) position directly to the tile x,y. In my mind this is the hardest to code, yet most efficient solution. On a square grid it's very easy to convert an (x,y) position to a square on the grid. However in a staggered column grid, you deal with offsets. I tried to calculate offsets using the a function that takes an x or y value, and returns the resultant offset y, or x. The Zig-zag graph of <a href="https://www.google.ca/search?q=graph%20of%20arccos(cos%20x)&amp;client=ubuntu&amp;espv=2&amp;biw=1366&amp;bih=687&amp;site=webhp&amp;source=lnms&amp;sa=X&amp;ved=0ahUKEwjLhvbRu7TLAhWLyIMKHVo-DXcQ_AUIBigA&amp;dpr=1#q=arccos(cos+x)" rel="nofollow noreferrer">arccos(cosx)</a> solved that.</p>

<p>Checking if the mouse was within the tile, using this method was difficult and I couldn't figure it out. I was checking whether the mouse(x,y) was beneath a <code>y=mx+b</code> line that was dependent on the tileX, tileY approximation(a square grid approx).</p>

<p>If you got to here, Thanks!</p>