9 Replies Latest reply on Apr 21, 2009 5:15 PM by kglad

    HitTest vs. mathematical intercept - Efficiency?

    Desprez10
    Desprez10 Apr 19, 2009 5:30 PM

      So I have a line-of-sight problem on a hex grid that can be computed by drawing a line and then seeing what hexes it intersects.

      The big issue is that HitTest will need to be run many times, and I understand that this computationaly intensive, and can slow things down markedly.

       

      So, I came up with a pure mathematical solution combined with pre-tests to rule out certian hexes before an intercept needs to be computed at all.

      Anyway, the various rules and tests are becoming quite good, and I'm finding I only have to run a handfull of intersect tests for any given line of sight problem, and these could also benefit a HitTest function. An additional benefit is that I also need a lot less actual movieclips on the stage, and this probably will speed things up all on its own.

       

      However, my actual intersect formula is more complex than I initialy anticipated. There seems to be no simple formula to see if a particular line intersects a particular hexagon. Rather, you test the line individualy against each side of that hexagon. (so, up to six tests unless you find an intersect early.)

       

      So the question is, are (up to) six line segment intercept formulas (pure math) worse (time computation-wise) than drawing a line, moving a hex, and performing a single HitTest? What are your impressions? How might I determine this without actually have to code everything twice and compare?

      • 1319 Views
      • Tags:
        • 1. Re: HitTest vs. mathematical intercept - Efficiency?
          kglad Adobe Community Professional & MVP
          kglad Apr 19, 2009 6:58 PM (in response to Desprez10)

          you're probably better off with the hitTest() especially if you can limit the number hexes to less than 100 by doing some rough estimates of which hexes are nowhere near the hit area and avoid tests on them.

           

          the main thing that slows flash is having a lot of movieclips/graphics.  so anything you can do to remove movieclips that are no longer going to be used is worthwhile.  in addition, you should check if enabling the cacheAsBitmap property of your movieclips will enhance performance.  for those movieclips that aren't scaled, faded, rotated and don't have timeline animation, this will be a major boost.

          • 2. Re: HitTest vs. mathematical intercept - Efficiency?
            Desprez10 Level 1
            Desprez10 Apr 19, 2009 7:21 PM (in response to kglad)

            Thanks for the reply.

            However, I think I just found a snag that is going to preclude hitTest alltogether.

            It's rather involved and probably not worth detailing, though. (Unless one finds detailed discussions abut LoS on hex grids unhealthly facinating. Heh.)

            • 4. Re: HitTest vs. mathematical intercept - Efficiency?
              Desprez10 Level 1
              Desprez10 Apr 19, 2009 10:13 PM (in response to kglad)

              The short version:

              For game mechanic reasons, the particular sides of a potentialy blocking hex the LoS line passes through are sometimes important. Sometimes, for a particular hex, they will determine which adjacent hex to also look at. (without going into too much detail)

               

              AFAIK, hitTest() will only tell me if a hex is hit, not where it is hit, unless I make every edge of a hex a potential object to hitTest() against. (correct me if I'm wrong). If that's the case, I'm looking at an efficiency comparison of 1 to 1 of hitTest() vs. intersect formula, as opposed to, say, 1 to 3 on average.

              1 hitTest vs. 1 intersect formula prolly puts the runtime win on the formula - unless I've been missinformed on the cpu cost of hitTest(), which I admit is certianly possible.

              • 5. Re: HitTest vs. mathematical intercept - Efficiency?
                kglad Adobe Community Professional & MVP
                kglad Apr 20, 2009 6:15 AM (in response to Desprez10)

                you're correct:  hittest can't be used to determine where an object is hit unless each part of the hit object is a movieclip and you loop through those parts using another set of hittests or use some other means to determine where an object is hit.

                • 6. Re: HitTest vs. mathematical intercept - Efficiency?
                  Desprez10 Level 1
                  Desprez10 Apr 20, 2009 5:56 PM (in response to kglad)

                  As a follow-up, I did some caluculations, and on my sample 7x7 hex grid, when computing LoS between 2 hexes, the intercept formula runs about 10-25 times, (depending on terrain) and sometimes 0 times for short ranges.

                  However, when looking at an 'all inclusive' LoS picture (that's LoS to all other 48 hexes) from a particular hex, the function runs about 300-700 times, and takes about 1/2 second on my old-ish machine. So hitTest() is probably less than ideal in that case anyway.

                   

                  So, the unit-to-unit LoS calculations should run pretty quick in the background, as they only have to perform a check on the hexes the units happen to be in. Whereas the comprehensive LoS test is nice to have to show the player visibility from a particular spot for planning purposes, and is not intended to run continuously in real-time.

                  • 7. Re: HitTest vs. mathematical intercept - Efficiency?
                    kglad Adobe Community Professional & MVP
                    kglad Apr 20, 2009 6:15 PM (in response to Desprez10)

                    if you want to decrease your calculations you could divide your stage into a rectangular grid.  each grid would contain say 4 hexes in their entirety and parts of others.

                     

                    you could then do a first pass LoS calculation to determine which grids to check and then check the hexes in those grids.

                    • 8. Re: HitTest vs. mathematical intercept - Efficiency?
                      Desprez10 Level 1
                      Desprez10 Apr 21, 2009 4:39 PM (in response to kglad)

                      I currently limit the area to check into 4 quadrants. Centered at the LoS origin, the target hex will only fall in one of the four, and that's the one you check.

                      I wanted to use 6 directions, in 60° cones (works well with the hex sides), but I messed up the code. So, until I need to revisit it, the 4 sections will work for now.