Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!


1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


AI-controlled beings finding ideal targets in a tile-based map


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
10 replies to this topic

#1 kobuscrispi   Members   -  Reputation: 126

Like
0Likes
Like

Posted 17 June 2006 - 08:22 AM

I am working on a game (Titled Zombie City Tactics) that requires enemy AI more advanced than I'm used to working with. One particular thing is giving me trouble - the enemy units selecting the best target to approach. Take this situation, for example: http://img.photobucket.com/albums/v26/professorscissors/targetfind1.gif The green square representing the moving unit, the red squares representing potential targets, and the gray squares representing walls. Now, a stupid AI would assume the target on the left was better, because it's two squares away, whereas the other target is three squares away. However, a decently intelligent AI would see it like this: http://img.photobucket.com/albums/v26/professorscissors/targetfind2.gif And see that when it comes to actualy path length, the target on the right is much closer. My problem is that I'm trying to find a way to do this *quickly.* My current method should work, but gets very slow in large maps with lots of beings. What it does is this: http://img.photobucket.com/albums/v26/professorscissors/targetfind3.gif The yellow squares are the spaces it is looking at, because they are next to green squares. If it doesn't find any targets there, it marks the yellow squares as 'explored' squares, and iterates again: http://img.photobucket.com/albums/v26/professorscissors/targetfind4.gif Still no targets, so it iterates one more time: http://img.photobucket.com/albums/v26/professorscissors/targetfind5.gif And then it find the target on the right, and selects it. It wouldn't find the left target for another 3 iterations. If no new yellow squares are added in one iteration, it assumes no target and gives up. This works fairly well, but has the downside that it takes HUGE amounts of time in large, open areas. Can anyone here suggest a preferable method? Thanks in advance.

Sponsor:

#2 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

0Likes

Posted 17 June 2006 - 08:57 AM

This article seems like what you are looking for

http://www.gamedev.net/reference/articles/article2003.asp

It deals with A* and to make the search shorter it starts the search from both the "red squares" and the "green square"

It also has some tips for speed boosting

#3 scgames   Members   -  Reputation: 2012

Like
0Likes
Like

Posted 17 June 2006 - 09:01 AM

It looks like you're basically re-inventing A* (more or less), so that may be a good term to google for (try 'A pathfinding', 'A star pathfinding', or '"A*" pathfinding). It can be computationally intensive, but there are various things you can do (such as computing paths over the course of a few updates, or computing the path iteratively) that can improve performance. I'm not sure, but I think A* and its variants are commonly used in RTSs and other tile-based games, so it should perform adequately under the right circumstances.

I don't have a lot of direct experience with A* though, so the above is partially guesswork. Also, there's an AI forum here on gdnet where subjects like this are often discussed; you might check there as well.

[Edit: The AP's link looks like a good place to start.]

#4 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

0Likes

Posted 17 June 2006 - 09:04 AM

^same guys^

on another note the title of your thread deals with an ideal target as you put it.

if your ai unit is a zombie shouldnt it go for the most open and easily seen target (the one on the right) regardless of the distance?

zombies are like people...lol...they go for what's shiniest not what's closest

#5 kobuscrispi   Members   -  Reputation: 126

Like
0Likes
Like

Posted 17 June 2006 - 09:15 AM

Actually, I am using A* for the pathfinding after it selects a target. But suppose there are 40 targets. Wouldn't it have to run the A* algorithm 40 times to find the closest one? If there are 40 humans and 40 zombies, that's about 1600 executions of A*, versus 40 executions of my algorithm. Is that really faster?

#6 Bob Janova   Members   -  Reputation: 769

Like
0Likes
Like

Posted 17 June 2006 - 10:55 AM

Is the zombie supposed to know where you are even if it can't see you? If not, you can just do a visibility test on each enemy in turn, and the closest visible enemy (or the one closest and in its line of sight, or whatever) becomes the target.

#7 kobuscrispi   Members   -  Reputation: 126

Like
0Likes
Like

Posted 18 June 2006 - 05:08 AM

It being a pretty abstracted strategy game, effective gameplay challenge requires that the enemy, like you, always knows where you are.

#8 Barius   Members   -  Reputation: 325

Like
0Likes
Like

Posted 18 June 2006 - 07:11 AM

You could precalculate the shortest path from every tile to every other tile using something like the Floyd-Warshall algorithm before each level.

#9 kobuscrispi   Members   -  Reputation: 126

Like
0Likes
Like

Posted 18 June 2006 - 09:13 AM

I dunno, on a (for example) 20x20 map, there's 400 tiles... storing the shortest path from every tile to every other tile would mean storing over 150000(!) values - 399 distances per tile!

#10 Bob Janova   Members   -  Reputation: 769

Like
0Likes
Like

Posted 18 June 2006 - 10:32 AM

Okay, scratch my previous response then! In that case I advise some sort of pre hoc (is that even a word? I mean either at load time or stored in the map file) merging of large open areas into 'megacells', and keeping track of which 'megacell' (maybe zone is a better word) each character is in. That should reduce the number of unnecessary checks you do.

#11 Barius   Members   -  Reputation: 325

Like
0Likes
Like

Posted 18 June 2006 - 10:56 AM

Quote:
Original post by kobuscrispi
I dunno, on a (for example) 20x20 map, there's 400 tiles... storing the shortest path from every tile to every other tile would mean storing over 150000(!) values - 399 distances per tile!

Yes, but that's only 300K if you use shorts. Modern PCs have tons of RAM, so why not use it?






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS