Sign in to follow this  

How to code the path of movement of an AI

This topic is 2666 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi all,

I have a question about coding the movement of an AI object. I am not looking for pathfinding, since the path is fixed for every object. I will give an example here: In a tower defense game, all the enemies will be walking on a specific path on the screen. So my question is, what is the best way to code this path.

I have a few ideas in mind, but I don't know which one is more standard(or both aren't standard) in this situation.

1. Hard code all the coordinates in a text file. which means, the enemy should change its position on the map according to what the file says per frame. For example: (10,20),(10,30),(10,40)...etc. This file could get really big relatively to the scope of the game. I don't think this is the right way.

2. Hard code just the fixed points where the enemy is heading to in order, then use simple pathfinding to move the object towards the destination. For example: the destination is (100, 50), (100, 100), (200, 100) and the starting point of the enemy is (10, 10). The enemy will move towards (100, 50), then (100, 100), then finally (200, 100). This seems like a good way, but the movements will be in straight lines only.

I hope I am not making the question too unclear. Please let me know if you know a good way in handling this.

Thank you for your advice and patience.

eAGLO

Share this post


Link to post
Share on other sites
Why not blend option number 2 with some dynamic pathing logic? Dynamic short-range pathfinding is a well-studied field of AI, and would let you do things like introduce formations, flocking type behaviours, crowding behind slower units (or pathing around them if you prefer), and so on.

Share this post


Link to post
Share on other sites
I poked the direction into the map in mine. Starting from the exit, do a breadth first search pointing all the new nodes at the old ones until you run out of empty cells.

This way you only need to do anything at all when you drop a new gun in the level, which means the creeps don't do any hardcore calculations at all. In fact they only read from a cell once when they first move into it.

This is how the original pacman games handled the ghosts running back to the centre hole, so it's hardly original. :s

Share this post


Link to post
Share on other sites
Plenty of ways to do this. Pathfinding might be the best solution, but you can do the same thing with input files for a game like this. For example, you could make a set of "rail" nodes. Place nodes at:
- start/entry points
- stop/exit points
- curves
- splitpoints

Each node tells where to go next. Eventually that can be multiple directions.

struct Pathnode
{
vector position;
NodeRelation nextNodes[]; // One or more paths to a next node
}

struct NodeRelation
{
Pathnode headingTo; // Next node to move to
int chance; // Optional, a chance this relation gets picked
vector headingDirection; // Sprite / movement direction. Can be calculated
// dynamically as well though
}

You only have to watch out not to make the path circular. You could avoid picking the same node twice for a given entity.


Another way might be using bitmaps. Probably the easiest way to define the exact movement coordinates, certainly if you have a curvy path. Once you have a visual map, draw a "rail" on top. For example, a red line is path1, a green line path2, and so on. For each possible color you could make an unique rail to follow.

You can import those bitmap(s) and generate nodes like explained earlier. Or simply let entities follow the line you drawed. For example, if an entity is placed at position XY, you can determine it's next step(s) by looking at the 8 surrounding pixels. Scan for a red(or another color) line, and skip the position you came from earlier.

Not the most beautiful solution, but I guess the focus is on making a fun game here, not to implement a stunning flexible pathfinding system.

Rick

Share this post


Link to post
Share on other sites
Hey Eagle,

The more line pieces you make over a specified distance, the less will it look like the monsters follow a line. So option 2 should be good. But agreed, implementing some dynamic pathing logic would be sweet, and add variation to the types of critters you send through.

In my opinion, many TDs lack in this aspect. typically the only movement-wise
difference between the units is the speed.

Don't do the frame-relative coords thing. At least, make it relative to the local
machine time instead of frames. In my opinion that would be better.

Share this post


Link to post
Share on other sites
Thank you guys, your input gave me a clear direction on my current project. Even though I still haven't decided how the exact code would look like, but it will look similar to the option 2, which most of you suggested.

Based my understanding, a Pathfinding algorithm is implemented when there is no pre-defined route. For example, in MMORPG, an aggressive monster will move towards the player's location when it sees one. So in a traditional tower defense game, when all the routes are pre-defined, how does Pathfinding act on the entities? It just finds the next node which is where the entity should move toward?

Sorry, I shouldn't raise a new question in another question.

Thanks again.

eAGLO

Share this post


Link to post
Share on other sites
More globally, a "pathfinding" algorithm tries a whole lot of options and picks the best one. The shortest route in this case. But it can also be used to check the possibilities in a chess game. However, to speed up, methods like A* focusses for the shortest route and therefore shall try to avoid other routes right from to the start.

To the point, pathfinding is indeed used to find the optimal route from point A to B. "Optimal" could be based on distance, but also on other aspects such as the type of ground. Cars prefer the road instead of sand for example. In addition, pathfinding also helps to avoid walking through walls, water or other (static) obstacles. To be aware of these obstacles (the environment), you'll need to generate a map of nodes and their connections with each other. Here is a nice tutorial that tells how to implement A*.
http://www.policyalmanac.org/games/aStarTutorial.htm

You can also use it for a TD game. You'll have to define a start and end point. A* will then calculate the best route from A to B. The best route is probably not the distance in this case, but the route that is protected the least. A* works like this:
- For each entry, exit, corner/curve and split point, insert a node (map coordinate)
- Connect the nodes with each other (A to B, B goes to C,D and back to B, and so on)
- For each connection, calculate the "weight". This tells the quality of this part of the route. You can base it on distance, but it's also possible to check which/how many towers are covering that piece of route. You can update all connection weights before a new wave of enemies starts.
- As for finding the path itself, see that tutorial. It works kinda like a floodfill, but orientated towards the end point.

However, I think letting the CPU choose a random route is more fun and therefore true pathfinding like A* may be overdone for a game like this...

Rick

Share this post


Link to post
Share on other sites
Quote:
Original post by eagleyeh
Thank you guys, your input gave me a clear direction on my current project. Even though I still haven't decided how the exact code would look like, but it will look similar to the option 2, which most of you suggested.

Based my understanding, a Pathfinding algorithm is implemented when there is no pre-defined route. For example, in MMORPG, an aggressive monster will move towards the player's location when it sees one. So in a traditional tower defense game, when all the routes are pre-defined, how does Pathfinding act on the entities? It just finds the next node which is where the entity should move toward?

Sorry, I shouldn't raise a new question in another question.

Thanks again.

eAGLO
Yeah, I've made my method public in a few questions about TD pathfinding and nobody seems to give it any credence. Despite it being cheap and efficient and requiring almost no cpu useage whilst the game is running. Oh well... :)

2) Would also work

Share this post


Link to post
Share on other sites

This topic is 2666 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this