next »

[Guard]

Let's say I have this 2D Array map

Code:

    { 0,0,0,0,7,1,1,1,1,1,1,1,1 },
    { 0,7,7,7,7,1,1,1,24,1,1,1,1 },
    { 0,7,24,24,24,24,24,24,24,1,1,3,1 },
    { 0,7,23,23,23,23,23,23,24,1,1,3,1 },
    { 0,7,24,23,23,23,23,23,23,1,1,1,1 },
    { 0,7,24,23,23,23,23,23,23,1,1,1,1 },
    { 0,7,23,23,23,23,23,23,24,1,3,1,1 },
    { 0,7,24,24,24,24,24,24,24,1,3,1,1 },
    { 0,0,0,0,1,1,1,1,1,1,1,1,1 },

and I have HashSet full of Integers that define blocked tiles. What would be a good way so that when I click on one part of the map from where my player is standing to do a good pathfinding? A* (using nodes/etc)? What do you suggest?

Thanks.

[st33d]

Use A* if it's just the player walking a path, but abort the search after so many cycles whilst keeping note of the best tile so far during the search.

If you click on a part of the map that is tricky to get to then your game will stutter as it exhausts every possible route on the map (especially if they click on an area impossible to reach).

[Ravine]

While i was working on a game designer-programmers collab competition in my school, consisting on making an AI for Pacman (best score wins, mine was #4 on 10), i used an A* implementation based on this paper http://www.gamasutra.com/view/feature/3317/smart_move_intelligent_.php?print=1 . (various listing available, click the links)

You can rely on this page too http://theory.stanford.edu/~amitp/GameProgramming/ which is kind of a reference on the A* subject, with various visual examples.

What i would do in that case :
1- determine your base data structure (the one you will iterate on)
2- populate carefully this ds
3- implement Djikstra's algorithm first
4- when it works, go for A* (which is Djikstra with heuristic)

You already have your "nodes" defined : your grid is a collection of nodes (with each tile is a node). Each can have a cost (sands take longer time to travel in while concrete is the fastest way to reach your goal) or not (each tile is 1 or 0 - can or cant walk on).

Here, because you already have this grid, use it as your data structure.

[Sigma]

check out this

http://www.policyalmanac.org/games/aStarTutorial.htm

i used this in one of my project

[TheSpaceMan]

If you want to save cycles but waste memory just save the path to each node from each node. This would require a static map that is quite small.

[Guard]

I'm lost. 

[Tycho Brahe]

Basically he means, at startup, run a* or Dijkstra on every node, to every node and then save the resulting paths into a structure.

The main problem I can see with it, apart from the altering problem obviously, is the massive amounts of memory required.

[Ravine]

ok, lets try to clear some stuff then

let say you have a map like that
 _ _ _
|_|o|_|
|_|_|_|
|_|_|_|
|_|x|_|

x is a critter who wants to reach o

If you implement something like a BFS, it will test each tile around, then a little bit further, etc, and will say "i've found a way" when it will reach the o


(from my gamasutra's link)

Now let's say your map has some more infos, like different surfaces with different walk speed. You want to take the shortest path in term of cost (time) not in term of distance. Then, you will need another algorithm. One which takes the cost in account. That's what Djikstra's do.

|1|o|4|
|1|4|4|
|2|4|4|
|1|1|1
|1|x|1|

intuitively, you see that the leftmost path is the "shortest" in term of cost ( 1 + 1 + 2 + 1 + 1 = 6) while right most is the longest, and the center one is the shortest in term of distance (3 tiles) but not in term of time ( 1 + 4 + 4 = 9 ).

Djikstra's algorithm will compute this path (the left one), since it takes the cost of moving in its computations. It's main drawback (it's still a good algorithm) is that it will test almost "all" the solutions available and will return the best one.

Then, you will think "hey, i need A*", and you may be right. A* just adds another fancy stuff to Djikstra's. It computes the "best" path, with a heuristic. The heuristic is an estimate of your current try while executing the algorithm. It says "your current path is not the best option right now, since you cost more than this estimate time, so go back, and try another path". I personnaly used the raw distance between my 2 points as a heuristic. (refer to gamasutra's or amit's page on A* for more infos).

Now that's said, the fact is : you need a data structure to scan and find those path. This datastructure can be a ds you've built upon your current tiling system (another array which holds the cost of each tiles for example), or your array, but with the info of the cost inside. Like in this pseudo code :

Code:

struct Tile
{
   int type;  // 1 represents the sand, 2 the grass, etc  -1 is a blocked path
   int cost;  // 1 is a quick tile, 2 is twice as long to walk on than 1, etc
}

You may just keep the type instead of storing type and cost, and have a function returning the cost for each type. If sand is always a quick tile, GiveCost(int tileType) will always return the same cost.

You test all the neighbours of your current tile by looking it's type, then push it in the Open nodes List mentionned in the gamasutra's article.

That said, you may see more clearly what it is all about.

For the memory considerations mentionned, dont care if you're working on PC. If you were on an embedded device with little memory, ok, you can care. But since i imagine your array of tiles will always be in memory, there's no need to worry about memory consumption since your active tiles (the one on the screen, which are the more likely to be test, which are a subset of a "world" tilemap) will be less than your big-array-of-tiles.


[quick edit] : just reread your first post and i dont get why you use a hashset of ints. Is there any specific reason you use this type of datastructure instead of a matrix ?

[Tycho Brahe]

I've found that an easy thing to do is to implement a flood fill algorithm first, then turn it into Dijkstra and then turn that into A*

A* isn't that hard to understand (not to me at least) but it is quite hard to implement from the off.

[Ravine]

I've found that an easy thing to do is to implement a flood fill algorithm first, then turn it into Dijkstra and then turn that into A*

A* isn't that hard to understand (not to me at least) but it is quite hard to implement from the off.

That's totally my point, and i'm giving this advice based on my experience (related to that pacman contest mentionned in my first post). I tried to jump to the A* directly, but couldnt wrap my head around. So i got back to the Djikstra's, made it working, tweaked my datastructures to be not time consuming, then i decided i'd leveled up enough to go with A*.

As mike acton says : it's all about data. Know your data, choose your data structures according to your problem

[frederiksen]

Basically he means, at startup, run a* or Dijkstra on every node, to every node and then save the resulting paths into a structure.

The main problem I can see with it, apart from the altering problem obviously, is the massive amounts of memory required.

just wanted to say you don't have to save the whole path, and if you run a dijkstra you already have the shortest way to all the nodes.

eg: if you have a dijkstra for the tile [2,2], x's are impassable:
[4|x|2]
[3|2|1]
[4|x|0]

if you are at [0,0] (left upper border) and want to go to [2,2] you only need the node with the lowest result which is [1,0]. If you have gotten to [1,0] you check and get [1,1]. So basically what you need is a one-dimensional array for every node you have with the length of how many nodes you have. Which is of course still a lot, but i think for nodes it's an ok solution (especially because i haven't mastered a* yet). For tiles it's perhaps a bit excessive.

[Ephphatha]

While i was working on a game designer-programmers collab competition in my school, consisting on making an AI for Pacman (best score wins, mine was #4 on 10), i used an A* implementation based on this paper http://www.gamasutra.com/view/feature/3317/smart_move_intelligent_.php?print=1 . (various listing available, click the links)

A bit too late for your competition, but Collaborative Diffusion looks like an excellent algorithm for a game with multiple AI agents like pacman.

[bart_the_13th]

I made this using floodfill algorithm only, the main drawback is that it only suitable for non-realtime games(ie. only for turn based games)
http://filebin.gamedevid.org/view/100ea/