Path on a Grid

So. I was challenged by a co-worker to write another AutoCAD game, this time it was in the vein of a Defense game. For those of you unfamiliar with the concept, it's quite simple: defend your tower from invading waves of enemies by placing defense structures (walls, turrets, and the like) in a grid.

Such a challenge could not go ignored!

Building a missile turret would be easy, I've practiced enough with my Missile Defender demo. Moving entities would also be easy, as well as creating them and the defense structures. I realized the difficult part would be giving the enemies the AI necessary to find the ideal path on the grid to the target area.

After much head scratching, and a little google search for inspiration on the logistics, I found the piece I was looking for. By creating a conceptual grid and choosing a target location on the grid (I call it a seed), I can determine that all adjacent cells to the initial seed will have a movement cost of 1 in order to get to the target area. Working outwards, I can then perform the same task on those adjacent cells; calling them "seeds", ignoring the target, all adjacent cells to them have a movement cost of 2, and so on and so forth.

Now, being that this will eventually be part of a game, the movement cost will have to be updated dynamically. That means, the function to determine the cell cost will have to be efficient, able to calculate the cost for the entire grid very quickly. For a 30 x 20 grid, the time is approximately 0.6 seconds (for my computer). This isn't bad, but it's not great. However, I know I am not the best at this, so to get to the point, is there any way to improve the efficiency?

Here's the code so far:

(defun make_creep_array( / i cost_array)
 ; Main function
 (setq i (getvar "cdate"))
 (setq cost_array (get_cell_cost '(((1 1) 0)) (make_level_array 30 20 nil)))
 ;(if (apply 'and (mapcar 'cadr cost_array)) (princ "\nSuccess! :D") (princ "\nFailure! D:"))
 ;(show_cost cost_array)
 (princ (* (- (getvar "cdate") i) 1000000))
 (princ)
 )

(defun show_cost(listy / )
 (mapcar '(lambda (x) (vl-cmdf "text" "j" "MC" (car x) 0.3 0 
        (cond ((numberp (cadr x)) (itoa (cadr x))) ((cadr x) "X") ((not (cadr x)) "D:")))) listy)
 ); Place text entites representing travel cost per cell

(defun get_cell_cost(seeds level / cost leaves flowers i)
 (setq cost (1+ (cadar seeds)))
 ; Plant seeds
 (foreach forVar seeds (setq level (subst forVar (assoc (car forVar) level) level)))
 ; Get leaves (adjacent cells)
 (setq leaves (apply 'append (mapcar '(lambda (x) (get_adjacent_cells x)) (mapcar 'car seeds))))
 ; Flowers (of the adjacent cells, all -valid- cells; within level, unoccupied and nil cost)
 (setq flowers (vl-remove-if-not '(lambda (x) (and (setq i (vl-position x (mapcar 'car level))) (not (cadr (nth i level))))) leaves))
 ; Flowers produce seeds (list of all flowers with associated status and updated cost)
 (if flowers
   (get_cell_cost (mapcar '(lambda (x) (list x cost)) (remDups flowers 0)) level)
   level
   )
 ); Calculate cost for each cell

(defun get_adjacent_cells(cell / )
 (list
   (list (1+ (car cell)) (cadr cell))
   (list (1- (car cell)) (cadr cell))
   (list (car cell) (1+ (cadr cell)))
   (list (car cell) (1- (cadr cell)))
   )
 )

(defun make_level_array(totX totY useCel / i j retn)
 ; where <useCel> is a list of used cells
 (setq i 1 j 1)
 (while (<= i totX)
   (while (<= j totY)
     (setq retn (cons (list (list i j) nil) retn) j (1+ j)))
   (setq i (1+ i) j 1)
   )
 ; Blank level is complete, now replace used cells using useCel
 (mapcar (function (lambda (x) (if (member (car x) useCel) (list (car x) t) x))) retn)
 )

(defun remDups(listy cntr / i)
 (setq i (nth cntr listy))
 (if i (remDups (cons i (vl-remove i listy)) (1+ cntr)) listy)
 ); Remove all duplicates in any given list

The function make_creep_array is currently set up to simply display the time it has taken to run.

My goal is to create a list for a 50 x 50 level in less than 0.5 seconds, preferably much less. Currently, it takes approximately 10 seconds. That goal is a little far-fetched, so a more reasonable goal would be to get the 30 x 20 case to below 0.4 seconds.

Also, I don't want this to be done for me. I'm just looking for advice and suggestions for the logic of it. I want to do the grunt work.

Thank you in advance. ^^

Dude,

Check this out

http://www.theswamp.org/index.php?topic=31050.0

Cool stuff, Lee, thanks a lot. I noticed Kerry linked to pretty much the same logical technique I was using, but I don't see a recursive function in his code (posted here: http://www.theswamp.org/index.php?topic=31050.msg366308#msg366308). I'll take a closer look. His code seems to move fast, but it's hard to tell with all the drawing of rectangles and whatnot.

Overall, is it better to use a recursive function where possible, or a while loop? Or, does it depend heavily on the situation?

Overall, is it better to use a recursive function where possible, or a while loop? Or, does it depend heavily on the situation?

Although elegant, the only advantage of a recursive loop is the reduced amount of code.

Recursive methods are slower as they have to run on the stack, and use more memory.

Although elegant, the only advantage of a recursive loop is the reduced amount of code.

 

Recursive methods are slower as they have to run on the stack, and use more memory.

Ah, I see. I'll try to re-write it using a loop. Thanks again. ^.^

Ah, I see. I'll try to re-write it using a loop. Thanks again. ^.^

You're welcome mate , good luck