Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » simple path finding

Credits go to Avenger, imaxcs, kentl, and ReyBrujo for helping out!
This thread is locked; no one can reply to it. rss feed Print
 1   2 
simple path finding
Matthew Leverton
Supreme Loser
January 1999
avatar

I'm looking for a simple path finding method. There are four tile types:

  • Grass

  • Woods

  • Castles

  • Rocks

Rocks must be avoided at all costs, because they are not passable. The other three contain the same move penalty, but you can hide in Woods and you have to fight Enemy castles. Therefore, the tile preference would be Woods or Friendly Castles, Grass, then Enemy Castles. However, the shortest route should always be taken.

So for any given route, the shortest paths around rocks should be determined. [Classic path finding.] Then I need to determine which of the paths have the fewest enemy castles. If more than one path has the same number of Enemy Castles, then I need to pick the one with the most Woods.

I know what I need to do—I'm just looking for some simple ways to do the initial path finding.

See my blog for more information.

imaxcs
Member #4,036
November 2003

I might be completely wrong, but why don't you do this (I suppose you use some sort of A*):
every time you check, which tile(s) is/are the best to step on next, also check, which type it is and add something to the cost (or make it completely unwalkable).

Avenger
Member #4,550
April 2004

Try hacking together some A* code from tutorials or such.. Or write your own. It is a hacking competition, right?:P

ReyBrujo
Moderator
January 2001
avatar

I did a very simple one for KQ, check movement.c. Not sure if it will be easier to just find another algorithm. The search_paths does the processing. The difference with A* is that this calculates the path assigning an "order id" to every square. You then begin moving the squares by finding the correlative numbers. So, if two squares are at the same distance, they both have the same "weight". You can use recursivity to find all the path combinations, and each time you "walk" a path, calculate the number of castles and the number of bushes.

In example, for this map (--- are walls, *** is target):

roberto@ansalon:~/src$ ./astar
(0, 0) to (13, 1)

001 002 --- 006 007 --- 017 016 017 ---             --- ---
002 003 004 005 --- --- --- 015 --- 017 --- --- --- *** 022
003 004 005 006 --- 012 013 014 --- 016 017 018 --- 020 021
004 005 006 007 --- 011 012 013 014 015 016 017 018 019 020
005 006 --- 008 009 010 011 --- --- 016 017 018 019 020 021
006 007 008 009 --- --- --- --- 018 017 018 019 --- 021 022
007 --- 009 010 --- --- --- 018 019 018 019 ---     --- 023
008 009 010 --- 014 015 016 017 018 019 --- 023 --- 025 024
009 010 011 012 013 014 015 --- --- 020 021 022 023 024 025
010 --- 012 013 014 015 --- --- 022 021 022 023 024 025 026
011 012 013 --- --- 016 017 --- 021 022 --- 024 025 --- 027
012 013 014 015 016 017 018 019 020 021 --- 025 026 027 ---
--- 014 015 016 017 018 019 020 021 022 --- --- --- 028 029
016 015 --- 017 018 019 020 021 022 ---         --- 029 030
--- 016 017 --- 019 020 021 --- --- ---             --- 031

The search begins at 001. *** can be 021 (if coming from down, which is 020, then *** must be 021) or 023 (if coming from the left). Note that, begining from 001, you have two 002. Using recursivity and linked lists you can translate all the tiles, and then check each list to see which one is better for you.

One last thing, if you transverse the path from lower to higher, you may end in a tile 021 or 023 which is not the final one (there are several of those). To prevent this, you need to walk the path backwards.

(Edited: added explain just in case)

--
RB
光子「あたしただ…奪う側に回ろうと思っただけよ」
Mitsuko's last words, Battle Royale

Matthew Leverton
Supreme Loser
January 1999
avatar

Is the common approach to just recursively walk every path? I suppose once I found a single path that worked, I could stop processing any path that gets longer.

ReyBrujo
Moderator
January 2001
avatar

Yes, if you could graphically represent A*, you would see "concentric circles" from the starting point to the end. It could be optimized by using A* from both ends, so that wherever the circles touch, the path is found.

I added some explanation to my previous post, just in case.

--
RB
光子「あたしただ…奪う側に回ろうと思っただけよ」
Mitsuko's last words, Battle Royale

kentl
Member #2,905
November 2002

Actually, the whole point with A* is that you will not see concentric circles from the starting point to the end. If thats your way of doing things you are probably doing some form of iterative deepening search.

If you implement A* the node (as it's a graph searching algorithm) with the lowest f value (f = g + h) will always be expanded. Where g could be increased with <terrain type cost> for each step and h use any admissable heuristic.

So..
g = parent.g + <terrain type cost for this square>
h = x_length_to_target + y_length_to_target

Is a good alternative..

A good link explaing it in detail
This link is more "hands on" and still correct/good

imaxcs
Member #4,036
November 2003

I doubt it will be useful for anybody, but here is my attempt at a path-finding algo:

1bool CPath::create_path(const CTile* tile, const CTile* target)
2{
3 // we have two containers, one for the openlist and one for the closedlist
4 list<CNode*> open;
5 list<CNode*> closed;
6 
7 // if the path hasn't been cleared yet, we do this now
8 clear_path();
9 
10 //cout << "*" << tile_distance(tile, target) << "*" << endl;
11 
12 // see, if we can return immediately
13 if (tile == target)
14 return true;
15 else if (!target->walkable())
16 return false;
17 else if (tile_distance(tile, target) > MAX_TILE_CHECKS)
18 return false;
19 
20 //cout << "Tile: " << tile->get_c() << " " << tile->get_r() << endl;
21 //cout << "Target: " << target->get_c() << " " << target->get_r() << endl;
22 
23 // add the current tile to the closedlist
24 closed.push_front(new CNode(tile->get_c(), tile->get_r(), 0, get_h(tile, target)));
25 
26 // create a target-node ( not in one of the lists ), so we can use target_reached() more easily
27 const CNode* tar = new CNode(target->get_c(), target->get_r(), 0, 0);
28 
29 // set the current node, which will be altered during the walk through the map
30 const CNode* cur = closed.front();
31 
32 while(!target_reached(cur, tar))
33 {
34 // some helper-variables, that make the commands shorter
35 unsigned c, r;
36
37 unsigned i;
38 
39 // add the surrounding tiles to the openlist (in a random order)
40 vector<unsigned> tmp(4);
41 for(i = 0;i < 4;i++)
42 tmp<i> = i;
43 random_shuffle(tmp.begin(), tmp.end());
44 for(i = 0;i < 4;i++)
45 {
46 c = cur->get_c();
47 r = cur->get_r();
48 if (tmp<i> == 0)
49 c++;
50 else if (tmp<i> == 1)
51 c--;
52 else if (tmp<i> == 2)
53 r++;
54 else if (tmp<i> == 3)
55 r--;
56 
57 if (CCampaignDatabase::get_instance().get_map()->tile_valid(c, r) && CCampaignDatabase::get_instance().get_map()->get_tile(c, r)->walkable() &&
58 !node_in_list(c, r, open) && !node_in_list(c, r, closed))
59 open.push_front(new CNode(c, r, cur->get_g() + 10, get_h(c, r, target), cur));
60 }
61 
62 // check, if the openlist is empty or the closedlist too full
63 if (!open.size() || closed.size() > MAX_TILE_CHECKS)
64 {
65 delete_list(open);
66 delete_list(closed);
67 delete tar;
68 return false;
69 }
70 
71 // put the node with the best f-value in the closedlist
72 list<CNode*>::iterator best_f = get_best_f(open);
73 closed.push_front(*best_f);
74 open.erase(best_f);
75 
76 // change the cur-variable
77 cur = *best_f;
78 
79 
80 /*cout << "OPENLIST:" << endl;
81 print_list(open);
82 cout << "CLOSEDLIST:" << endl;
83 print_list(closed);
84 int tmp;
85 cin >> tmp;*/
86 
87 }
88 
89 /*print_list(closed);
90 exit(-1);*/
91 
92 // coming here, it means that there is a valid path
93 // now track back the way to the start by accessing the parent and save it in the path-variable
94 while(cur != closed.back())
95 { // while start not reached
96 const CTile* tile = CCampaignDatabase::get_instance().get_map()->get_tile(cur->get_c(), cur->get_r());
97 path_.push_back(tile);
98 cur = cur->get_parent();
99 }
100 
101 // clean up
102 delete_list(open);
103 delete_list(closed);
104 delete tar;
105 
106 return true;
107}

It might be slow as hell and buggy compared to others', but at least it's mine...;)

kentl
Member #2,905
November 2002

Seems okey imaxcs, but as

get_best_f()

isn't in there we can't know if you take into account different tile costs or use the

f = g + h

formula correctly to expand the most likely nodes (and thus not get the concentric circles search which you generally want to avoid).

imaxcs
Member #4,036
November 2003

Well, the get_best_f()-function only iterates through the list and returns the node with the best f-values ( f being stored already in the node). However, as in my game, no diogonal movement is allowed, I store f when the node is created, of course by using g + h;

ReyBrujo
Moderator
January 2001
avatar

From what I see, Matthew wants to apply the heuristic after finding the shortest paths, not while looking for it. In other words, find all the shortest paths, then see which one is the best for the AI (and if he has several AIs, the wiser may choose the one with less castles and more woods, the average will choose randomly, and the dumbest will choose the one with the more castles).

--
RB
光子「あたしただ…奪う側に回ろうと思っただけよ」
Mitsuko's last words, Battle Royale

kentl
Member #2,905
November 2002

To me it looks like a misunderstanding of how to attack the problem. By making the square cost differences small enough he can still be sure that the shortest number of steps are taken as well as that the other requirements are met. And still use A*.

He doesn't say anything about using this for different enemy AI:s. And even if he would like to, he could use A* with a bit of tweaking with the g value in f = g + h. (g could be set randomly within a certain range when the node is first introduced in the open list, more random = less intelligent behavior).

Anyway. As time is of essence and Speedhack is going on using any technique that is good enough would do. But this is the best one (mathematically proven), period. ;)
[edit] Corrected errors. Also, hope that I am not coming of to harsh, it's a problem I have. I would have smiled if I said it instead of wrote it. :)

imaxcs
Member #4,036
November 2003

Why do it afterwards? When there are two tiles, which have the same f-value, the smart one should pick the one with the better type on it, the average rolls the dice and the dumb one picks the worst.

kentl
Member #2,905
November 2002

Actually, the f-value should be lower if there would be a "better type on it". Equal f implies equally good squares to expand during the search.

You are right about "Why do it afterwards?" though. No need for that really, it's just a time waster. My suggestion in the previous post skips the whole "afterwards" thing in the algorithm as well as giving the optimal search efficiency.

Matthew Leverton
Supreme Loser
January 1999
avatar

The original game had no path finding at all. It just moved up/left/down/right depending on if source x was larger or smaller than destination x.

Part of the strategy then, is commanding your troops. You cannot just say go from X to Y and take no thought. Because troops can only move 5 tiles per turn, sometimes you have to tell them to only go 3 tiles, because otherwise you'd hit a rock, etc.

What I want to do is keep that general idea, but eliminating running into a rock. So, the shortest path must be picked every time, regardless if that means you move into a castle.

So if from A to B there are two paths, and one of them means you have to move through three castles, and the other four grass tiles - it should pick the castles. However, if there are an equal number of tiles to move, it should pick the one that is the "best". However, I suppose I could be nice and treat the distance as multiples of 5, since that is how far you can go in one turn.

I suppose I could still do it in one fell swoop, but I would have to keep track of two things: weight and distance (turns), because the lowest weight value doesn't mean that's the path it should take.

To further complicate the matter, there are other troops that are moving about. Ideally, they would try to avoid them as well, but I'm content to ignore that. However, it would be sort of funny watching your troops avoid hitting a castle, only to run into an army beside it. ;)

kentl
Member #2,905
November 2002

It is how I understood you. It can be done easily with A* it's just a matter of giving the correct <cost per square>.

You want the cost of walking through a castle higher than on grass. But not so much higher that a longer route (more steps) would be taken even if it was through pure grass.

Example A - Map:
F = From, G = Grass, C = Castle, T = To

FCCGG
GCCGG
GGGTG

Let V = 1 / (MAP_WIDTH * MAP_HEIGHT + 1) = 1 / (4*3 + 1) = 1/13 = 0.076923

By this formula V could never affect the route as the max route length is 12 steps and V only gives 1/13 more cost to each step.

Example A - Same map, the cost values for each square:
F = From, 1 = Grass, 1.076923 = Castle, T = To

F 1.076923 1.076923 1 1
1 1.076923 1.076923 1 1
1 1        1        T 1

Now you have an ordinary map, which you could use a normal A* to get the route with the lowest score.

Walking only on grass (the way you do not want it) would give you:
route1 = SOUTH, SOUTH-EAST, EAST, EAST
cost(route1) = 1 + 1 + 1 = 3

While walking through the castles (the way you want it) would give you:
route2 = SOUTH-EAST, SOUTH-EAST, EAST
cost(route2) = 1.076923 + 1 = 2.076923

As you can see this is nice! And, it allows you to use A* and get the fastest search with optimal route to take. That you only will take the X first steps does not change anything, just take them, they will be optimal.

Also, even if there would have been 12 castle squares to the goal:
cost(12-castles) = 1.076923 * 12 = 12.923076
it would be cheaper than 13 grass ones:
cost(13-grass) = 1 * 13 = 13

You follow my line of thought? This is both an exteremely easy way. And it lets you work with well known algorithms that are proven to be efficient.

The above can look like you should render a 2D map first with the above values and then use A*. But you don't of course. You use the normal formula f = g + h but g is defined as:

g = parent_move.g + cost_of_this_square

Where cost_of_this_square is 1 for grass and 1+(1/13) för castles (in a map with 12 squares in it).

h could use the normal heuristic h = x_length_to_target + y_length_to_target

[edit] Added some info and correct an error.

[append]

This can be extended to trying to avoid troops as well. But it gets more complicated as the 1/13 you have to "give out" as additional costs would be shared between castles and enemy troops.

It could be:
cost_of_this_square = square_cost + troop_cost
square cost = 1 for grass and 1/13 * 0.7 for castles
troop_cost = 1/13 * 0.3 if a troop is in the square, otherwise 0

And extended further to have "heavy troops" and "light troops". Where heavy troops should be avoided even more than light troops. In this case the heavy and light troops would have to share the 1/13*0.3 if it's still as much more important to avoid a castle than a troop as before.

Then it could be:
troop_cost = 1/13 * 0.3 * 0.6 if heavy troop, 1/13 * 0.3 * 0.4 if light troop and 0 if no troop...

Hm, I am getting carried away here.. :)

Matthew Leverton
Supreme Loser
January 1999
avatar

Quote:

You want the cost of walking through a castle higher than on grass. But not so much higher that a longer route (more steps) would be taken even if it was through pure grass.

That should work for what I need. I'm not planning on getting over complex, as anything is better than the original game. I may or may not implement path finding this weekend. I've finished the core part of the game, and am feeling somewhat lazy at the moment. ;D

kentl
Member #2,905
November 2002

Glad to be of help, we'll see what happens then. Hm, sort of wish I could have joined Speedhack (because I have never joined anything like it), but I have an exam on monday. :)

Johan Halmén
Member #1,550
September 2001

I might include some path finding in my speedhack game. In that case I rewrite something I have in a square tile based game. My speedhack game has hexagonal tiles, but it shouldn't matter. I've reinvented the wheel, i guess, with the following algo.

If you want to travel from tile A to tile B, you begin with placing a step value of 999999 in each tile. Then you start with B and place a step value of 0 there. Then you recursively check each neighbour cell and place a one higher step value in them and a path direction pointer to this tile. Don't touch a neighbour tile that has a lower step value than the one you would place there. This is the case that breaks the recursive run.

Don't touch a neighbour tile if it is unpassable. And you can use the step value as the penalty. I haven't used that, but I guess it works. 10 for a normal tile, 5 for a friendly castle (if it is worth visiting), 20 for hostile castle.

After parsing, each tile holds a pointer to one neighbour tile, a pointer that shows the cheapest path to B. So this is a good algo if you have more than one character that wants to go to B.

One IOTD confuses more than a thousand words :)

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Years of thorough research have revealed that the red "x" that closes a window, really isn't red, but white on red background.

Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest.

kentl
Member #2,905
November 2002

Johan: I have also invented exactly that algorithm before I knew about how A* worked (as well as I do today). Swedish minds think alike? ;) And you are right that it's a good one if you have multiple units that what to go to the target.

Matthew Leverton
Supreme Loser
January 1999
avatar

I got A* working. Took me a few hours to get it, because I wasn't expecting it to be so simple to implement. I had to restructure my data types a bit to handle it better. You can all laugh at the implementation when I release an updated version. ;)

For now I am just weighting things at 8/9/10/15. It seems to work well. Ideally, I'd allow for several modes of sending troops:

  • maniac - don't bother avoiding castles if it's extra moves,

  • normal - avoid all enemy castles except the target

  • stealth - hide in woods at all cost

However, I don't want to over complicate the simple interface with tons of options.

Johan Halmén
Member #1,550
September 2001

I never implemented my path finding in my hexagonal tile map as I intended. I just made a simle hack and it turned out to work very well. From one hexagon tile you can go to six different directions. The black daemons that are chasing Maw (our guy) just check each of the six directions, to see if he is there. If he is there (standing on the same row) they go after him. In the next turn he can hide from them by stepping off the row. Any better path finding than that would have made the game too difficult.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Years of thorough research have revealed that the red "x" that closes a window, really isn't red, but white on red background.

Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest.

kentl
Member #2,905
November 2002

Quote:

For now I am just weighting things at 8/9/10/15

I am afraid that I don't understand what you mean here. :)

Quote:

I never implemented my path finding in my hexagonal tile map as I intended.

Well nothing says that game quality will increase proportional to the efficiency of the enemies. :) Just look at Pac-Man.

Peter Wang
Member #23
April 2000

I just wanted to say that the algorithm described by Johan Halmén is (more or less) Dijkstra's pathfinding algorithm.

Johan Halmén
Member #1,550
September 2001

I'm the founder of WRIS, Wheel Re-Inventers' Society.

[EDIT]
Sorry, but you can't join the society. Everyone has to found their own society.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Years of thorough research have revealed that the red "x" that closes a window, really isn't red, but white on red background.

Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest.

 1   2 


Go to: