Searching a map for a path
by Scott Coursey · in Torque Game Builder · 12/18/2005 (9:46 pm) · 2 replies
I'm working on a T2D turn-based strategy game. I have quite a bit done already, up to the point where I would like to start working on the AI.
I really like the AI setup I have: The AI "player" consists of an object which controls the general behavior of all the units. The units on the field themselves get a chance to "think", where they ask questions of the AI "player". Depending on the answers, certain actions are taken (ie, if the AI thinks it has a better chance to win, it can increase the chance a unit will have of knowingly getting destroyed in battle, instead of retreating for health).
Anyway, I'm getting ahead of myself... My AI plans are just that: plans.
So, to start it all off, I want the AI to be able to look at the field and examine the units, find paths from place to place, etc. To do this, I need a script which will do some searching.
Ultimately, I would like to use an A* search, but I don't know how to do that one. I do know how (off the top of my head) to do a depth-first (or is it breadth first? I can't remember) search. It's pretty simple, and for many instances, it's rather fast.
I wrote one up, encapsulated it into a class and am providing it for a hopeful starting point for others. Yes, I know it's not the world's best code, but I like it.
The search expects to receive certain inputs, as well as find a global variable.
The global is "$obList", which is of type SimSet. It simply lists all the units in the game. Those will be used as points of avoidance. You can also include anything else in here that you want the search to avoid (water, lava, trees, etc).
The inputs to the RunSearch() is %startPos and %endPos. Each of these are positions, as would be returned from a sprite (ie, "10 10").
The movement used is purely square - no diagonals are used, but that would be rather simple to change (adjust the "offsets" variable inside the AddNeighbors function).
Like I said, I'm sure there are problems. I know I've found at least one map setup that will constantly return "no path" when I can clearly see one. To prevent the algorithm from searching an extremely long time, I put in a global variable, "$MAX_SEARCH_STEPS_ALLOWED". Those are the maximum number of iterations of the main loop that will be examined; that is, the total number of neighbors that will be visited.
I didn't provide this as a resource, since it's definitely a WIP and I didn't feel like it. =P
You can find the search on my Web site.
I really like the AI setup I have: The AI "player" consists of an object which controls the general behavior of all the units. The units on the field themselves get a chance to "think", where they ask questions of the AI "player". Depending on the answers, certain actions are taken (ie, if the AI thinks it has a better chance to win, it can increase the chance a unit will have of knowingly getting destroyed in battle, instead of retreating for health).
Anyway, I'm getting ahead of myself... My AI plans are just that: plans.
So, to start it all off, I want the AI to be able to look at the field and examine the units, find paths from place to place, etc. To do this, I need a script which will do some searching.
Ultimately, I would like to use an A* search, but I don't know how to do that one. I do know how (off the top of my head) to do a depth-first (or is it breadth first? I can't remember) search. It's pretty simple, and for many instances, it's rather fast.
I wrote one up, encapsulated it into a class and am providing it for a hopeful starting point for others. Yes, I know it's not the world's best code, but I like it.
The search expects to receive certain inputs, as well as find a global variable.
The global is "$obList", which is of type SimSet. It simply lists all the units in the game. Those will be used as points of avoidance. You can also include anything else in here that you want the search to avoid (water, lava, trees, etc).
The inputs to the RunSearch() is %startPos and %endPos. Each of these are positions, as would be returned from a sprite (ie, "10 10").
The movement used is purely square - no diagonals are used, but that would be rather simple to change (adjust the "offsets" variable inside the AddNeighbors function).
Like I said, I'm sure there are problems. I know I've found at least one map setup that will constantly return "no path" when I can clearly see one. To prevent the algorithm from searching an extremely long time, I put in a global variable, "$MAX_SEARCH_STEPS_ALLOWED". Those are the maximum number of iterations of the main loop that will be examined; that is, the total number of neighbors that will be visited.
I didn't provide this as a resource, since it's definitely a WIP and I didn't feel like it. =P
You can find the search on my Web site.
#2
All you have to do is set the tileCustom Data in the tiles, to be passable, blocked, or "weighted" so the path will try to avoid those squares. Then you just pass in start and end points, and you can get path positions back.
I supports having many paths active on the same map at a time, curved paths, path node optimizations. It will also draw debugging symbols so you can see what tiles its searching, and what path it generates.
Resource is here:
www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=9711
02/24/2006 (4:29 pm)
I also made a pretty robust C++ A* object for T2D. It's based on a tileLayer. All you have to do is set the tileCustom Data in the tiles, to be passable, blocked, or "weighted" so the path will try to avoid those squares. Then you just pass in start and end points, and you can get path positions back.
I supports having many paths active on the same map at a time, curved paths, path node optimizations. It will also draw debugging symbols so you can see what tiles its searching, and what path it generates.
Resource is here:
www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=9711
Torque Owner Chris Labombard
Premium Preferred
This is a Torque 2D implementation of the A* pathfiniding algorithm.