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.
|improve this question
\$\endgroup\$
  • \$\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 '10 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\$ – Marc Müller Jul 28 '10 at 4:42
  • \$\begingroup\$ See the edit I've added \$\endgroup\$ – Dani Jul 28 '10 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 '10 at 7:12
  • \$\begingroup\$ Can the title be a bit more informative, please? \$\endgroup\$ – tenpn Jul 28 '10 at 18:45
4
\$\begingroup\$

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

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ How can i profile flash project in flex? \$\endgroup\$ – Dani Jul 28 '10 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\$ – Jonathan Fischoff Jul 28 '10 at 4:55
  • \$\begingroup\$ Thanks, really helped me find the problematic part(wasn't in the algorithm, see comment on question) \$\endgroup\$ – Dani Jul 28 '10 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.

|improve this answer
\$\endgroup\$
  • 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 '10 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 '10 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\$ – edA-qa mort-ora-y Apr 27 '11 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 '11 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\$ – edA-qa mort-ora-y Apr 27 '11 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.

|improve this answer
\$\endgroup\$
  • \$\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 '10 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 '10 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.

|improve this answer
\$\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.

|improve this answer
\$\endgroup\$
  • \$\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 '11 at 17:26
  • \$\begingroup\$ Thanks for letting me know. I didn't notice the dates. \$\endgroup\$ – jhocking Apr 26 '11 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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