A* Pathfinding Woes

[Osteel]

EDIT: This thread has been solved. Check my final solution product (as a result) here! (http://devworld.ca/Tactics/MoveExamples.html)
Thanks!




Honesty. I'm about to kill myself.

I've been trying to work on pathfinding for the last month and in the many attempts, I just can't seem to get it working although I've come close. I've looked online, and have read the famous article (http://www.policyalmanac.org/games/aStarTutorial.htm) and ... I get it!

I understand how A* Pathfinding works; calculating F=G+H is no problem for me, and storing them in the openList, finding the lowest fCost and storing it into the closed list is not an issue (I don't think).



I just ... need someone to walk me through this from scratch. I think I've been going about it with my own perspective and (bad) understanding of pathfinding that I just can't think outside the box. I don't know what else to do anymore and I'm getting really discouraged, yet determined to get a very simple (that's all I need!) working pathfinding engine going.

So ... someone ... please help me out and help me figure this out. Or at least a hug. I need a hug.

[dandylion13]

Have you had a look at Keith Peter's Advanced ActionScript 3 Animation book? It explains it very well and includes working code for A*.

[Osteel]

I'm actually making a game in AS2.

I'm progressing pretty well on my Isometric Tactics game, and as you can probably imagine, am in need of a very simple pathfinding engine. I mean, simple as in, no diagonals and at max a 5 tile movement.

I'm not travelling long distances, nor am I moving multiple units ... so it just needs to be BASIC. And honestly, it's just halted my progress of my game the entire last month, and I'm extremely frustrated because I don't want to end up losing another project.



http://devworld.ca/5movement.jpg


As you can see from this image, I'm highlighting all the 'reachable' tiles from the center as seen in a traditional tactics RPG game. However, pathfinding is needed to then determine which of these tiles are visible to the player when objects are in the way.

I was able to muster this: example (http://devworld.ca/Tactics/pathfinding.swf)


As you can see, it's a 2D representation of the isometric grid. Click the black button at the top right twice and it'll display all 'reachable' tiles. You'll quickly realize that some of the tiles that should be reachable are not highlighted.

Pathfinding issues ...

So, that's where I'm stuck. I need to start from scratch.

[Valaran]

If you're going for line of sight, Im not sure a pathfinding algorithm is your optimal choice. Just circling outwards from the player (5 steps in each direction) checking all the tiles would suffice, and be much less costly than throwing in pathfinding in the picture.

Please excuse me if I misunderstood you, and while at it, if you insist on a working A* example, I could provide you one, but know that it would be in AS3.

I highly recommend that you switch over to AS3 while you're at it :)



Good luck!

[_sluimers_]

You're in luck, but can you help me out as a retribution? I don't know if my code is very efficient for path-finding, but it's probably very similar to what you are looking for.
Okay, for the weird names, for my top-down real-time adventure game I imagined my characters are able to detect the player circular due to his footsteps.
Thus the name of this function is (b)road(c)ast a (W)eb(o)f(S)ound. I haven't tested it yet, but I've made a very similar LineOfSight function, with the only difference being really being a line of sight (in multiple directions).
Basically it should be most useful for your situation.
Terrain adjustment is not included yet, but with a few tweaks it should be possible to get that as well.

If someone sees flaws in the code or thinks it can be done better, please say so.



public function bcWoS():void {
// pp = path points
// pd = path dirs
// np = next points
// nd = next dirs
var pp:Array, pd:Array = [], np:Array = [], nd:Array = [];
pp = onp.slice();

const m:Map = engine.map;
const mw:int = m.mapWidth, ms:int = m.mapSize;
const newHearabilityTiles:Array = [];
var obs:Array = m.obs, hearabilityTile:int;

// the number of steps left
var stepnoise:int = stepnoise;
const id:int = id;

var xyz:int; // xyz of point
var txyz:int; // xyz of next point (more temporary)

var d:int = 0; // direction
var nextDir:int, oppDir:int;
var n:int = pp.length;

// let's go in all directions
for (var i:int = pp.length; i--; ) {
pd[i] = ALL_DIRS;
}

for (;; ) {
if (!d) {
if (!n) break;
n--;
xyz = pp[n];
d = pd[n];
}

/*
* directions are in bits
* for example 1101 means the pathpoint in question
* wants to expand LEFT RIGHT (not up) and DOWN.
* at the end of the switch the most right bit turns 0
* and the loop repeats again until no direction are left.
*/
switch(1) {
case d >> DOWN & 1:
d = d ^ DOWN_BIT;
nextDir = ALL_BUT_UP;
oppDir = UP;
if (mw + xyz % ms - ms > -1) continue;
txyz = xyz + mw;
break;
case d >> UP & 1:
d = d ^ UP_BIT;
nextDir = ALL_BUT_DOWN;
oppDir = DOWN;
if (mw - xyz % ms > -1) continue;
txyz = xyz - mw; break;
case d >> RIGHT & 1:
d = d ^ RIGHT_BIT;
nextDir = ALL_BUT_LEFT;
oppDir = LEFT;
if (!((xyz + 1) % mw)) continue;
txyz = xyz + 1; break;
case d >> LEFT & 1:
d = d ^ LEFT_BIT;
nextDir = ALL_BUT_RIGHT;
oppDir = RIGHT;
if (!(xyz % mw)) continue;
txyz = xyz - 1; break;
}

// if we see an obstruction
if (obs[txyz]) continue;
// if we're boldly going to somewhere we've gone before
if (pp.indexOf(txyz) != -1) continue;

np.push(txyz);
nd.push(nextDir);
sendHearability(txyz, id, oppDir, stepnoise);
newHearabilityTiles.push(txyz);

if (!n && !d) {
n = np.length;
stepnoise--;
if (!stepnoise) break;
pp = np.slice();
pd = nd.slice();
}
}

// removing old tiles
for (i = hearabilityTiles.length; i-- ; ) {
hearabilityTile = hearabilityTiles[i];
if (newHearabilityTiles.indexOf(hearabilityTile) == -1) {
removeStepnoise(hearabilityTile, id);
}
}
hearabilityTiles = newHearabilityTiles;
}

[_kp]

I support Valarans oppinion, that pathfinding isn't the best choice. It is not exactly what you need here, at least not for the part where you check if a tile is reachable or not.

You don't really need to get a path to a specific point. Of course you could check all points in range if there is a path to the center (or the other way around), but you'll see that many paths will overlap or clearly never reach the center. There are many unnecessary calculations in this solution.

I would use simple recursive function. Let it start from the tile where the player stands. It takes a tile and a step counter that decreases each call. It returns if the tile is either impassable or already reachable or the counter is 0. Otherwise it marks the tile as reachable and calls itself with every tile around the current tile.

edit: actually on second thought, this could lead to errors if the maximum distance is too long in some cases ...

[Osteel]

Hi guys,

You're right in that it is, in a sense, a 'line of sight' way of determining all the reachable tiles (in this case, 5). However, I believe pathfinding is still needed in it's most basic sense to move to the selected tile. And if it's going to be used there, it might as well be used to determine which tiles are reachable.

Of course, as someone mentioned, the smart idea would be to pathfinding to the further tiles, and anyones 'passed' are automatically added to the reachable array; no point in checking them twice.



Regarding AS3. I know I should be using it, and I understand OOP from doing it with Java. However, for this game I'm not worried about lag, or issues optimization as it's a turn based Tactics games. That means one character moves at a time and grids no bigger than 20x20 (or maybe slightly larger).

I would have probably started it in AS3 though ... but I don't want to go through it all and rewrite it/learn my way through AS3. Perhaps the next project once this is done? :)



Now ... back to pathfinding. I found some pseudo code online, though I'm still having trouble understanding some of it. I just can't wrap my head around the part where it 'repoints the Gcost to the parent'. Here's the pseudo:



create the open list of nodes, initially containing only our starting node
create the closed list of nodes, initially empty

while (we have not reached our goal) {
consider the best node in the open list (the node with the lowest f value)
if (this node is the goal) {
then we're done
}
else {
move the current node to the closed list and consider all of its neighbors
for (each neighbor) {
if (this neighbor is in the closed list and our current g value is lower) {
update the neighbor with the new, lower, g value
change the neighbor's parent to our current node
}
else if (this neighbor is in the open list and our current g value is lower) {
update the neighbor with the new, lower, g value
change the neighbor's parent to our current node
}
else this neighbor is not in either the open or closed list {
add the neighbor to the open list and set its g value
}
}
}
}



Can anyone elaborate this, or add points that the writer might have assumed in his pseudo?

[TOdorus]

Hi guys,

You're right in that it is, in a sense, a 'line of sight' way of determining all the reachable tiles (in this case, 5). However, I believe pathfinding is still needed in it's most basic sense to move to the selected tile. And if it's going to be used there, it might as well be used to determine which tiles are reachable.

Of course, as someone mentioned, the smart idea would be to pathfinding to the further tiles, and anyones 'passed' are automatically added to the reachable array; no point in checking them twice.

Errmm... these are quite ineffective ways of going about solving the problem. A* actually visits tiles more than once already to get one of the optimal paths instead of a path. What you should look into is an adaption of the Dijkstra's algorithm. Just extend from the centre. Per extension you check which tiles can be reached and which tiles cost to much.

You have two lists. One open list and one closed list. The open list contains the next tiles to be checked. The closed list contains all the tiles that are visited. Per tile on the closed list every tile needs to store this information: the total cost to get there and the previous tile in the path.



//
//INITIATE
//
You put the start tile in the open list.
You set the costs for every tile type
//for a vehicle with wheels it costs 3 to move through grass and 1 to move over a road, for example
//you can also use a impossible cost of -1 or antyhing <= 0 to tell the algorithm that the tiletype is inaccesable for the unit
var totalMovementPoints:int //the maximum amount of movement for the unit
var movementPointsLeft:int
//now you can start the loop
for(i:int = 0; i <= totalMovementPoints; i++){
//
//EXTEND
//
per tile on the openlist{
movementPointsLeft = totalMovementPoints - openTile.cost
get all the neighbors of the open tile. //Check for duplicates! If you find one, check which has the lowest cost to reach the tile.
//since you have four directions you have four neighbors max
per neighboring tile {
calculate the cost to move into that tile.
if(theCost + movementPointsLeft < totalMovementPoints){
//the unit can move that far
add the neighbor to the openlist
}
remove the tile from the openlist and put it into the closed list
}
//
// CHECK
//
if(openList.length == 0){
done, now the function can return the closedlist.
}
}


The closed list contains all the information you need. If you need to know which tiles to display as reachable, just loop through the open array. If a player hovers over a tile and you want to display the path the unit will take, every tile has information of the previous tile in the path. Just work your way back until you get back to the start. To show the cost just read it off the tileinfo in the closed list.

EDIT:
actually valaran and kp already suggeted this, but you seem intent on using a pathfinder to check the outer tiles. Not only would this be ineffecient, it would probably not visit all the tiles the unit can possibly reach as they aren't considered for the solution to the single goal a pathfinder has.

[Osteel]

Hi,

I have a read a little about Dijkstra's algorithm in this blog post here. (http://www.gamedeveloperskills.com/?p=13&cpage=1#comment-9). Does this mean that it basically goes from the starting point and branches out in all directions until the end point is found?

[TOdorus]

As far as I know the Dijkstra Algorithm is just the branching out from a single node until a certain condition is met. Most of the time just a number of extensions from the centre. In your case the condition would be until an extension would only be possible to tiles which are to expensive.

You need to realize that you have no endpoint. You're looking for all the possible tiles that can be reached. The pseudocode I provided has an algorithm which will give you that, and the cost and path to get to a tile. The one on the blog works basicly the same, but has another ending condition.

[Osteel]

Yeah, you're right.

I've saved your Pseudo and am in the processing of trying to make it settle in my brain. Please help me try to understand if, if you have time. Here is what I make of it:


1. Just like any pathfinding engine, you have an openList and a closedList. Currently, the only tile on then openList is the start tile.


2. Searching the openList array, you look for the lowest gCost value. Currently it'll only be the start tile. With this new 'current tile', you look at the four surrounding tiles around it and:

i) If they are not on the openList, that is, they have never been looked at, you place them onto the openList with their gCost and their parent tile, that is, the current tile you're sitting on since it's being looked at from there.

ii) If the neighboring tile is already on the openList, that is, has already been examined before, compare its gCost with the gCost is WOULD have had it come from the current tile you're sitting on. If it's greater, change it's gCost to what it would be from the current tile, and switch it's parent tile to the current tile because it's a shorter path to THAT neighboring tile.


3. Once done searching the neighboring tiles, add the CURRENT TILE to the closedList and remove it from the openList (to not be looked at again).


4. Repeat by finding, again, the lowest gCost in the list. There will definitely be matching gCosts, but it doesn't matter, just choose the first lowest one.


5. END the loop when the openList is empty, that is, all the tiles have been looked at as a CURRENT TILE and added to the closedList with all the parents pointing to the right direction. OR if the neighboring or current tile is the target tile.




Amendments/Questions:

1. However, like you said, there is no actual 'target' in this. It is simply looking at all the tiles and if they're within movement range. And when the user selects the tile to move to, you simply use the closedList to find the target tile and backtrack via the parents.


2. In the algorithm, gCost = 10 for horizontal and vertical movement. However, in this case, it would be equal to 1, and neighboring tiles will only be considered if:

i) They are NOT on the closedList

ii) The are walkable

iii) Important: If they gCost is <= to the character movement. As in the above example image in the first post, it would be a movement of 5.




How does this sound?

[_kp]

So, to get back to the recursive function solution, I made a quick test.

It is basically what I've have described with one addition: A tile is not marked as reachable but gets a distance value. If it is checked again, the functions goes on, if the current distance is less than the tiles one (means: the tile has been reached by using a shorter way and so checking continues).

Here's the function, it's not exactly actionscript but I think it is easy to modify the syntax:


function testMove(tile:Tile, distance:Int) {
distance--;
if (distance < 0) return;
if (tile == null) return;
if (!tile.passable) return;
if (distance <= tile.distance) return;
tile.distance = distance;
testMove(tile.left, distance);
testMove(tile.right, distance);
testMove(tile.top, distance);
testMove(tile.down, distance);
}

You can see the result here: http://www.swfcabin.com/open/1270675206
(click anywhere to reload the tiles and start from a random position, modified settings update after click)

[TOdorus]

I should really make an animation to explain this properly, but that will cost me too much time, so sorry if this isn't clear yet. You're on your way, but still basing yourself on pathfinding sources I see. I'll point out what needs to be changed. That is, if you need more than what _kp has provided already, as it doesn't allow for variable tilecosts (roads costs less than grass to move to).


2. Searching the openList array, you look for the lowest gCost value. Currently it'll only be the start tile. With this new 'current tile', you look at the four surrounding tiles around it and:

(...)

4. Repeat by finding, again, the lowest gCost in the list. There will definitely be matching gCosts, but it doesn't matter, just choose the first lowest one.



You don't look for the lowest gCost. You need to extend all nodes.

I see that I've made a mistake in my pseudocode. Not that it won't work, but it isn't as clear as to how it works. What you should add is a openList and a nextOpenList. First you work your way through ALL the nodes on the openList, not just the ones with the lowest cost (just checking that one is a pathfinding optimization). You add the new nodes to nextOpenList and when the openList is empty, nextOpenList becomes the new openList and you repeat the proces until your ending condition is met.

The nextOpenList is unnecessary, but it may help you understand what's happening.


5. END the loop when the openList is empty, that is, all the tiles have been looked at as a CURRENT TILE and added to the closedList with all the parents pointing to the right direction. OR if the neighboring or current tile is the target tile.

You don't need a target tile (if you're creating a turn- and tilebased game)

Note that you won't need a target tile as both the AI and player would be using the same algorithm to determine what moves it can make. The AI needs to know what moves are possible first to make a decision. Since that means running the algorithm, all possible paths are alread known and you don't need a pure pathfinder. True pathfinding is only necessary in realtime games. So the only condition would be an empty nextOpenlist or Openlist in this case.



2. In the algorithm, gCost = 10 for horizontal and vertical movement. However, in this case, it would be equal to 1, and neighboring tiles will only be considered if:

i) They are NOT on the closedList

This doesn't allow for variable costs

You say you can understand A*, so I advise against doing it like that. This will work for your problem, but you can easily tweak it to have it work for variable costs per tiletype and per movementtype (tracks move well over everything, wheels only over roads and badly over the rest).

If you don't use variable costs any path is as efficient as any other. If you DO have variable costs, there can be a more efficient path to the tile. Since A* already incorperates this concept I suggest you implement it and make your algorithm much Much more versatile. For example, I can reuse my own A* algorithm for any nodebased game I'll make, which has saved me a bundle of time on projects.

To accomplish this, you need to add some stuff per extension. Check the tiletype and look up how much it costs for the unit. Add it to the G cost of the parent and you've got the G cost of the child. It's that easy.

The next addition is that you still need to check it if it's on the closed list. The alternative parent, could provide in a lower G cost so you need to follow the same proces and compare if it is really lower. If it is, overwrite the nodes data.

[Osteel]

I need to apologize. I'm at that point in creating this movement system where I've read so much on pathfinding that I've embedded in my mind what I understand it as and clearly not what it's supposed to be. But I'm so far in that I find it hard to think outside the box. Thanks for the discussion though.


Moving on. What you're saying is, you simply look at all the tiles in the openList in one go rather then picking the lowest, checking the neighbors, checking the next lowest and so on and so forth? Just from openList[0] to openList[length], you just go through each and point their parents and store their gCosts until all the tiles are checked on the grid (or in this case, all the tiles within [X] amount of gCost)?



Secondly, lets assume that my game requires no terrain costs. Would it be smart to go with what kp created as a way of checking reachable tiles? By the way, kp, thanks so much for creating and providing the pseudo code, it's awesome.

[TOdorus]

Moving on. What you're saying is, you simply look at all the tiles in the openList in one go rather then picking the lowest, checking the neighbors, checking the next lowest and so on and so forth? Just from openList[0] to openList[length], you just go through each and point their parents and store their gCosts until all the tiles are checked on the grid (or in this case, all the tiles within [X] amount of gCost)?

Yeah. Although in code this would translate into an openlist with length 0 and not extending when the G of the child becomes to high.


Secondly, lets assume that my game requires no terrain costs. Would it be smart to go with what kp created as a way of checking reachable tiles? By the way, kp, thanks so much for creating and providing the pseudo code, it's awesome.

Yes, kp's way would be the way to go.

I'm assuming you'll have AI, so I'll take this a step further. For your AI to make decisions there must be several options and a way to evaluate them. Now say that you have the AI operate at the same level as the player (= the general/tacticion) If you create a game with the only choice being where to walk and what attack to use, this makes for few options. Your AI will be showing a lot of the same behavior. This isn't necessarily a bad thing (I still think Mario has some of the best applications of AI ever), but in a strategy game this can make the game a bit bland and the AI will be predictable. With little options you can actually let the AI loop through all possible moves and pick THE best move everytime (in the timeframe of one turn only).

You can also let the AI units decide individually what their best move is. This means decisions are taken on another level than the player does (individual). This won't make for THE best move as one unit can already have moved and block the more suitable units attack route. The upside to this is however, that you can have a tweakable AI which has certain strengths and weaknesses the player can exploit/fall victim to. Say you want a agressive AI, than they will always charge the closest enemy unit. A artillery AI will always keep a certain distance between the closest enemy unit and attack that one. A assasin AI will always work it's way toward the general unit. And so on, and so on.

How is this related to the possible moves algorithm? By scoring tiles on more criteria than just the cost to get there. This will give you an interesting read.
http://www.cgf-ai.com/docs/straatman_remco_killzone_ai.pdf (Dutchpride!)

[Osteel]

Alright!

So in conclusion we've determined that kp's method of determining the movable areas would be best by, instead of using a pathfinding algorithm. I'll begin working on understanding and applying the pseudocode he provided and will ask my questions here since this thread is already created.


Regarding AI. I've saved your linked PDF for when the time comes to apply AI. It was actually next on the to do list once I figured out basic movement. However, I've already considered how to work AI, though now that you explained it, may not be the best idea. Although, I'll run it through you here:


I was going to use a system of AI tactics and create, for each, a set of rules on how to apply the tactics. For example:

Melee: Closest
Would target the nearest enemy (or player unit) and move to an adjacent tile in order of the rear, either of the sides, and lastly the front, depending on what was available. It would then proceed to run the battle engine based on it's melee stats.


By setting up a list of tactics and instructions, I would in a sense, have a library to pick and choose from to apply to the different enemy units that the player would face. In terms of how the AI would choose which to pick from?

Well, when creating the actual sprites and enemy unit information such as their general stats, movement speed etc; I would also define to it three tactics to choose from in order of priority. Therefore giving some dynamic decisions, but not to the extend of full AI.

For example, a healer unit's tactics may be in order of:

1. Heal lowest HP unit in range.
2. Magic attack nearest enemy unit.
3. Melee attack nearest enemy unit.



In terms of movement, they would each have one of the following:

1. Aggressive - Rush the player
2. Neutral - Stand or move to nearest player
3. Coward - Keep your distance and move away from nearest player unit




What do you think? It's just a rough idea and outline, I haven't actually thought it completely though. For now, I need to work on kp's psuedocode.

[TOdorus]

That would be using some sort of state machine. Check if requirements are met and switch to that strategy. I would try to not define tactics. A tactic is applicable to a certain situation. You may have quite the diversity of situations in a strategy game. I try to have parameters that can add up to a "best decision" (best isn't really the best but more on that later). This is a bit more complex, but more fluid and dynamic. I think it approaches Fuzzy Logic.

Say you have a agressive character, the best decision would be the most agressive decision, right? But does it always need to be totally agressive? Say you have a mage unit, with both healing and agressive magic. There are certain situations that the decision between agressive and defensive can be less clearcut. Do I save one of my dudes, or kill one of his dudes?

Say the mage is geared for healing and the choice is between a weak friendly unit and a strong enemy unit. The choice is simple, but not to an AI which only takes the alternate strategy when the primary strategy can't be applied. The defense versus attack can be operationalised by simply evaluating the attack stats of each creature and see how much you gain and lose with each decision.



Gain = attackscore //friendly unit
Gain = -attackscore //enemy unit


Given that you first make a list of all possible decisions. This makes the mage more dynamic.

Now you can also tweak the weight of each input, to give a unit personality. Say we want a mage that is a bit more agressive.



agressivePreference = .3
Gain = attackscore *(1-agressivePreference*.5) //evaluating friendly unit
Gain = -attackscore *(1+agressivePreference*.5) //evaluating enemy unit
//or another way to write it
Gain = attackscore //evaluating friendly unit
Gain = -attackscore *(1+agressivePreference) //evaluating enemy unit


This mage will be 30% more prone to "kill his dude" when confronted with that choice.


Now this is a very simple example, but say the mage will be more prone to run away when under threat and that health plays a role in this.



//distance evaluation
fleePreference = -.1
balanceOfPower = sum(nearby friendlies attackScore) - sum(nearby hostiles attackscore)
prefDistance = balanceOfPower * (1+fleePreference) - hp

//healing evaluation
agressivePreference = .3
Gain = attackscore *(1-agressivePreference*.5) //evaluating friendly unit
Gain = -attackscore *(1+agressivePreference*.5) //evaluating enemy unit


(It's also a idea to standerdize values to only be 0 to 1 or -1 to 1. If I define balanceOfPower = sum(friendlyAttackScore) / sum(enemyAttackScore), than 0 = enemies are in total control and 1 = friendlies are in total conrol. This makes it easer to interpret)



Now the mage can evaluate per tile and base a score on:
how far it is from the preferred distance to the heat of battle
how close it is to a teammate to heal
how close it is to a enemy to attack
You can imagine you can add a lot to this stuff. The value of healing can also be made more complex by adding the balanceOfPower of the units into the equation with the hp that the targets have left.

The point is that you start defining actions, not tactics. The prefence for one or another action defines the tactic. This makes the units more dynamic and their decisionmaking more fluid. It also creates an AI that is harder to exploit, as you'd have to simulate a situation to some detail to create the same input (and get the same behavior).

The fun part is, that even you as a coder can't really predict what you're AI is going to do exaclty, but you can identify it's tactic. This is basicly what a player needs: an AI that is coherent in it's actions, but not quite predictable. This creates an AI the player can understand as it makes logical choices, but still is challenging.

This may all be a bit to much for you, in which a state machine can also perform strategic AI. It will however be a but more dogmatic in its decisionmaking.

[Osteel]

Wow ...

What you're suggesting is obviously the best course of action, allowing the AI to choose the path based on dynamic decisions. So in other words, when the AI is making a decision, it examines first all the friendly units around it and calculates their attackScores. It then examines the nearby enemy units and does the same?

Based on a comparison, and some complex math, you let the AI determine one of the following:

1. To attack the enemy units.
2. To assist the friendly units.
3. To move away from the battle and do any of the above two if possible along the way.


Creating an algorithm for that is going to take some work. Fortunately I have some people helping me with the game project who are pretty decent at math (I'm most definitely not) and will hopefully be able to figure out some algorithm of determining the AI. I also understand the need for standardizing numbers to be used in the algorithm such as:

Aggressiveness, where 1 = Very, 0 = Neutral, -1 = Coward, for example.


I'll tackle that once I reached that stage. Back to kp's example!



I've taken his pseudo and attempted to recreate it. This is what happens when I do, it only draws out to once side. Click this link: EXAMPLE (http://www.swfcabin.com/open/1270688320). The code used is as follows and I'm obviously missing something, but I tried my best to follow the pseudo:




row = 16;
col = 16;

startRow = 9;
startCol = 9;

charMove = 5;


findPath = function(tileName, distance){
distance --;

getRow = substring(tileName,2,2)
if (substring(getRow,getRow.length) == "_"){
getRow = Number(substring(getRow,0,1))
}

getCol = substring(tileName,tileName.length-1,tileName.length)
if (substring(getCol,getCol.length-1,1) == "_"){
getCol = Number(substring(getCol,2))
}



if (distance < 0){
return;
}

if (getRow > row or getRow < 1 or getCol > col or getCol <1){
return;
}

if (passable[getRow][getCol] != 1){
return;
}


_root["b"+getRow+"_"+getCol].gotoAndStop(9);
findPath ("b"+getRow+"_"+(getCol-1), distance);
findPath ("b"+getRow+"_"+(getCol+1), distance);
findPath ("b"+(getRow-1)+"_"+getCol, distance);
findPath ("b"+(getRow+1)+"_"+getCol, distance);

}

findPath("b"+startRow+"_"+startCol,charMove+1);



The code for placing the tiles is not added there, but I don't think it's relevant. Just know the variables: row/col are used in drawing the grid.

Suggestions?

[_kp]

Using strings is a quite a hack in my opinion...
Wouldn't it be less confusing if you had an multidimensional array which uses two integer coordinates to get a tile?

Anyway since it does work at the top and left I think something fails when you call the function again. getCol/getRow are Strings as far as I can see. I don't really know what happens if you decrease a string by one, it seems to work - but if you are using the + operator, the number 1 is probably converted into a string and it is interpreted as "b"+getRow+"1"+"_"+getCol


By the way, the code is actually written in haxe. I hope you see how much clearer this object oriented approach is. You don't have to use OOP of course, but I still advise you to at least make a step forward and don't use strings that much. Simple numbers are better to read, operate with and faster. :)

[Osteel]

Yeah, I see what you're saying.

The reason I'm formatting it now as "brow_col" (b1_1), is because it'll be easy for me to integrate this movement code straight into the game program which I already have going which uses that naming convention already.

I did a trace (typeof()); though, and it all returns number, so it's doing the calculations based on a number and not a string. Still, not sure why it's only doing one side of the circle haha.


On the other hand, I've started progressing on TOdorus' pseudo alongside kp's, just to see which I can get working, and get the feel for both approaches. Here's what I have so far for TOdorus' approach, though it freezes on the second loop:



findPath = function(){
// Cycle through all elements on the openList
for (i=1;i<openList.length;i++){
//Determine the row and col value of this currentTile
tileName = openList[i][2]
getRow = substring(tileName,2,2)
if (substring(getRow,getRow.length) == "_"){
getRow = Number(substring(getRow,0,1))
}

getCol = substring(tileName,tileName.length-1,tileName.length)
if (substring(getCol,getCol.length-1,1) == "_"){
getCol = Number(substring(getCol,2))
}


//Store the four surrounding tiles from this currentTile
checkTile = new Array("0");
for (o=1;o<=4;o++){
if (checkSide[o] == "row"){
checkTile[o] = "b"+(getRow+checkNum[o])+"_"+getCol;
}else if (checkSide[o] == "col"){
checkTile[o] = "b"+getRow+"_"+(getCol+checkNum[o]);
}
}


/* With the neighboring tiles selected. Loop through all four and see if it passes the test:
1. Is a walkable tile : passable[row][col] == 1;
2. Is not on the closedList : has been checked already;
3. Is reachable : gCost is <= charMove

If conditions are met then:
1. Store the gCost, tileName and parentTile into openList.*/

for (o=1;o<=4;o++){
getRow = substring(checkTile[o],2,2)
if (substring(getRow,getRow.length) == "_"){
getRow = Number(substring(getRow,0,1))
}

getCol = substring(checkTile[o],checkTile[o].length-1,checkTile[o].length)
if (substring(getCol,getCol.length-1,1) == "_"){
getCol = Number(substring(getCol,2))
}

// 1. Is it walkable:
walkable = false;
if (passable[getRow][getCol] == 1){
walkable = true;
}

// 2. Is not on the closedList
onClosed = false;
for (p=1;p<closedList.length;o++){
if (checkTile[o] == closedList[p][2]){
onClosed = true;
}
}

// 3. Is reachable
reachable = false;
if (openList[i][1] + 1 <= charMove){
reachable = true;
}



/* If conditions are met store the gCost, tileName and parentTile into openList.
Add the current tile to the closedList and take it out of the array*/
if (walkable == true and onClosed == false and reachable == true){
holdOpen[holdOpen.length] = new Array ("|",openList[i][1]+1,checkTile[o],openList[i][2]);
}
}

// Place the current tile on the closed list.
holdClosed[holdClosed.length] = new Array ("|",openList[i][1],openList[i][2],openList[i][3]);
}

/* Once all has been cycled through:
1. Move all tile from the holdClosed to the closedList
2. openList now stores whatever is in holdOpen
3. Refresh the variables*/

// 1. Move holdClosed to closedList
for (i=1;i<holdClosed.length;i++){
closedList[closedList.length] = new Array ("|",holdClosed[i][1],holdClosed[i][2],holdClosed[i][3]);
}

// 2. Move holdOpen to openList
for (i=1;i<holdOpen.length;i++){
openList[i] = new Array ("|",holdOpen[i][1],holdOpen[i][2],holdOpen[i][3]);
_root[holdOpen[i][2]].gotoAndStop(9);
}

// 3. Refresh variables
holdOpen = new Array (new Array("|"));
holdClosed = new Array (new Array ("|"));
}

[TOdorus]

TonyPa's tilebased tutorials (http://www.tonypa.pri.ee/tbw/). (The 2D array is pretty much standard in Flash tilebased development)

Well when looping through an array you should start with 0, as this is the first item in an array. This also makes it fit with your loop condition i < length.

I find it very hard to read through your code as it's such a unconventional map format, plus it's a lot of code to just go looking for bugs without a proper debugger. Soooh, at what line does it crash, and what variables come up undefined?

[Osteel]

Yeah, I have a very unconventional way of writing code. That's what happens when you're self taught and never actually learnt the proper way, you just develop your own way of doing things. Don't worry about debugging it for me, I won't make you suffer through it.

However, I'm continuing to make progress, so hopefully I'll have something to show in a few hours. :)

[Osteel]

Ah, I think I realize why my variation of kp's code only showed up one direction, and why my TOdorus code isn't working properly either. As we know, I'm naming my tiles using the following convention b1_1 b1_2 etc, and in doing so, have to determine the individual parts that make up the row/col values.

Therefore, I created this code:



getRow = substring(tileName,2,2)
if (substring(getRow,getRow.length) == "_"){
getRow = Number(substring(getRow,0,1))
}

getCol = substring(tileName,tileName.length-1,tileName.length)
if (substring(getCol,getCol.length-1,1) == "_"){
getCol = Number(substring(getCol,2))
}

Which substrings the name, and determines the individual digit of each. Now let's consider that we're starting on tile b9_9 as our start tile, and when the overall function is ran, we need to look at the four surrounding tiles from this point. Therefore, upon tracing getRow+"_"+getCol, we return:



8_9
9_10
10_9
9_8



Now, we do our thing with these four neighbors, storing them into the openList and checking them etc. That's fine and I am pretty sure I have that already covered in my code. However!, it is when the numbers become larger than 10 (>=11) that the values start screwing up.


For example, when running the code again, it'll look at all the open neighbors which are listed above and look at the surrounding for those. If we take the neighbor 9_10 and look at the neighbor directly to the right of it, we know that it'll be 9_11. However, when the getRow/getCol section is run for the above neighbors, we return:



7_9
8_10
9_9
8_8
8_10
9_01
10_10
9_-1
10_9
10_10
10_9
10_8
8_8
9_9
10_8
9_7


Notice any values above 10 result in some weird return, either a 01 or a -1. And since I used this codes in kp's interpretation, I assume that's what's causing it to only go to the top left, since the right, and down result in tiles that are greater than 10.

By the way, same results will happen for the row as well, but the above is the example of the col messing up.

Thoughts?

[Osteel]

SUCCESS!

Ah, so happy right now. I've finally managed to rewrite the code, figured out my issues and created:

Moving Example (http://www.swfcabin.com/open/1270774205)
(Click the top black button to run the calculation. Objects (black squares) are randomly placed, refresh to regenerate)


So grateful for you guys, TOdorus/kp for the help and support. I guess from here I simple make an example file where you can click any tile and it'll draw out the path using the parents stored in the closedList. Shouldn't be hard, simple loop.

However, the next step is now to allow height. Since it's a tile based tactics game that we're making, there's going to be height involved. I already have a height system put in place, from the map editor/creator, and will just integrate that into making moves.

I believe (and really hope), it's as simple as adding it to the 'neighbor tests' that I have in place now (such as , 'onClosed', 'within distance', etc). We'll see how that goes.



Either way, you'll probably see me back here soon either to show the next stage in the movement engine, or to ask questions about it. Also, will most definitely be starting a discussion on calculating AI (TOdorus, that's you ;)). I have a friend who's good at Math and has a programmatic mind and he seemed interested in making some calculations.

Thanks again guys! :love_heart:



EDIT:

I've made it so that you can click the tile and it'll draw the path using the parents stored.

[TOdorus]

Looking good Osteel


However, the next step is now to allow height. Since it's a tile based tactics game that we're making, there's going to be height involved. I already have a height system put in place, from the map editor/creator, and will just integrate that into making moves.

I believe (and really hope), it's as simple as adding it to the 'neighbor tests' that I have in place now (such as , 'onClosed', 'within distance', etc). We'll see how that goes.

Well, that's not that hard really, if you've used the dynamic cost algorithm. Just check how much higher the tile is and add that to the cost.

To be honest I've never done AI that advanced as I've never created turn-based games, but I'll see what help I can provide.

[Osteel]

Great!

Just thought I'd link this as well. It's a more visually appealing version which now consider's height (+/- 2 stacks) as well. The maps were also created using the map editor I made, saved and imported using the buttons, so that demonstrates the link there as well.

Moving Examples (http://devworld.ca/Tactics/MoveExamples.html).


My next step is to actually put in an animated sprite, though I don't think that'll be too hard either. I'll get started on it tomorrow after my exam. ;)

[furrymak]

Check this out?
http://tbg.tonypa.pri.ee/tut03.html