9
\$\begingroup\$

I'm making a Tower Defense game in Flash with no predefined path.

Although my grid is 40x40 (small?), A* is struggling when recalculating every time. So I made my own modification to ease the recalculation and the touched cell count dropped to around 900 (when modifying near the root). It still freezes for a very short, but detectable, amount of time when a new tower is placed.

Is this an implementation problem, or is 40x40 just too much?

Edit:

The structure of my code:

  • All the data is saved in 2d array of cells.
  • Each cell contains its parent in path direction (1-8 clockwise) and bitwise encoded array of its children in path (every bit represents a child).
  • The search is performed by A* with the estimate of euclidian distance.
\$\endgroup\$
7
  • \$\begingroup\$ You're going to need to be much more specific here. We have no idea what your code looks like, how it's structured, etc, and so we can't draw any conclusions about what's making it slow. \$\endgroup\$
    – Sean James
    Jul 28, 2010 at 4:34
  • 1
    \$\begingroup\$ When I implemented A* for the last time I remember it running through a 64x64 grid in at most 1ms. So yeah, it appears to be a problem with your implementation. I suggest posting your code or the gist of it so we can help you further. \$\endgroup\$ Jul 28, 2010 at 4:42
  • \$\begingroup\$ See the edit I've added \$\endgroup\$
    – Daniel
    Jul 28, 2010 at 4:54
  • 1
    \$\begingroup\$ If 40x40 is too slow, chances are good you're doing something very wrong. Either post your code or profile it. Alternatively, scale it up and see what happens - if an 80x80 grid takes more than four times as long, you've got something extremely broken in there. \$\endgroup\$
    – ZorbaTHut
    Jul 28, 2010 at 7:12
  • \$\begingroup\$ Can the title be a bit more informative, please? \$\endgroup\$
    – tenpn
    Jul 28, 2010 at 18:45

5 Answers 5

4
\$\begingroup\$

I can't comment, but first profile in Flex, everything else is conjecture.

\$\endgroup\$
3
  • \$\begingroup\$ How can i profile flash project in flex? \$\endgroup\$
    – Daniel
    Jul 28, 2010 at 4:46
  • \$\begingroup\$ Yes and no. I don't think you load the flash project directly. I think you might be able to profile the swf without source and still get function level info though. I would do a google search for "profiling a flash project in flex" or the like. I did and got this: flexblog.edchipman.ca/… which looks promising. \$\endgroup\$ Jul 28, 2010 at 4:55
  • \$\begingroup\$ Thanks, really helped me find the problematic part(wasn't in the algorithm, see comment on question) \$\endgroup\$
    – Daniel
    Jul 28, 2010 at 23:31
13
\$\begingroup\$

I'm assuming that TD is 'Tower Defence'

I think A* is going somewhat overboard for this.

At the start of the game, flood fill the game area from the exit points to create a movement map:

 |---------|
 |5|4|3|3|3|
 |5|4|3|2|2|
->5|4|3|2|1->
 |5|4|3|2|2|
 |5|4|3|3|3|
 |---------|

and movement is always towards a square with a lower value.

When the player places a tower, update each of the eight adjacent squares: for each square, set it's movement value to one more than the lowest adjacent value. If the value changes, repeat the process centred on the updated square. Then, to check that the route to the exit is not blocked, ensure all squares are adjacent to a square of a lower value.

When the player removes a tower, set the movement value to one more than the lowest adjacent square and repeat the process above.

A simpler approach would be to re-do the flood fill.

\$\endgroup\$
7
  • 6
    \$\begingroup\$ Re-doing the flood fill is more expensive than doing A* for a small number of units - roughly, the length of the board - at least in algorithmic terms (and since this is Flash, non-algorithmic constants like memory layout probably can't be used very effectively). However, this is a very good model for many communicating units, and is called collaborative diffusion - scalablegamedesign.cs.colorado.edu/wiki/Collaborative_Diffusion. \$\endgroup\$
    – user744
    Jul 28, 2010 at 17:27
  • \$\begingroup\$ @Joe Wreschnig: wow nice link. I've used that technique before but never knew what it was called. Thanks. \$\endgroup\$
    – tenpn
    Jul 28, 2010 at 18:17
  • \$\begingroup\$ @Joe, so long as there are at least a few barriers in the map I don't think this would be more inefficient than calling A*. That is, I believe only for a wide-open, nearly barrier free map with few units might it be worse. \$\endgroup\$ Apr 27, 2011 at 10:43
  • \$\begingroup\$ @edA: By definition a flood-fill must eventually touch every accessible point on the map; A* provides proven upper-bounds to how many points it must touch, which is at most every accessible point on the map and usually far less. The flood fill is a simpler algorithm to optimize things like memory layout for, but like I said, in Flash that probably doesn't matter. \$\endgroup\$
    – user744
    Apr 27, 2011 at 10:57
  • \$\begingroup\$ @Joe, that's what I'm arguing is that even with just a handful of towers the A* will likely touch nearly all of the spaces. But for N monsters it need only exceed total_squares/N to be less efficient than the flood fill. \$\endgroup\$ Apr 27, 2011 at 11:04
2
\$\begingroup\$

Strange, I thought I replied to this, but the reply seems to be gone. Make your search algorithm such that it can be updated in multiple steps, so that when you place a tower and play an animation, you can do a little bit every frame and you'll have somewhere between half a second and a second to update your A* without a noticable pause. It's latency - iF you can't speed it up, find a way to hide it. Playing an animation while placing a tower would be natural for a game and imo a good place to hide it.

\$\endgroup\$
2
  • \$\begingroup\$ This is a good idea in general, but bad for this specific question. A* on such a small grid should be nearly instant, not taking a significant amount of time. \$\endgroup\$
    – davr
    Jul 28, 2010 at 19:14
  • \$\begingroup\$ Fair enough. It's the only answer I could give that would solve the problem without knowing implementation details that would cause the slowdown. \$\endgroup\$
    – Kaj
    Jul 28, 2010 at 20:20
0
\$\begingroup\$

For a start you could change your array to a vector - should give you some speed improvements. Post the code and we might be able to suggest more optimisations.

\$\endgroup\$
0
\$\begingroup\$

I would guess that your slowdown is because you are calculating a path for all characters simultaneously. Calculating a path for one character is fast but if there are two dozen characters in the scene then that can bog down.

Instead you should spread out the load over a few frames. Stagger your AI updates so different characters update their path on different frames. It would be really noticeable if a character didn't react until a second later, but just one frame is not going to cause bad reactions.

\$\endgroup\$
2
  • \$\begingroup\$ This was answered nearly a year ago, and was only bumped because of Grace's editing work. (It had nothing to do with too many characters.) \$\endgroup\$
    – user744
    Apr 26, 2011 at 17:26
  • \$\begingroup\$ Thanks for letting me know. I didn't notice the dates. \$\endgroup\$
    – jhocking
    Apr 26, 2011 at 17:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .