next »

[Sigma]

hey guys,
          Recently i went through dijkstra algorithm and A* algorithm i understands the logic behind but i have problem in implementation. In tutorials every one is explaining the algorithm with a simple graph with weights defined i.e ok. for example my enemy is some where on the field and my protagonist is some where inside a building (say ground floor) and there are obstacles like walls and so on. To get my enemy to that point what are the procedures ? Procedures as in which data structure i should use trees or simply arrays. How to declare weights? whether it must be precalculated? some pseudocode please..... I'm a noob in Ai programming so just give me something basic that will give me a good kick start.

[mcc]

I don't really have anything helpful to say here so instead I'm just gonna link this article.

[nikki]

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
bear in mind that you use linked list as data containers, (atleast that's what i do)
http://en.wikipedia.org/wiki/Linked_list

when your list has some data waypoints, the weight is just an assignment. as in weight=w,  you  can always add weights when your feeling better.



at bcc; I found that articlle a long time ago, and then forgot where i found it; Great !

[powly]

Yeah mcc, that's definitely something I'll read carefully.

I think Sigma meant the weights as in how they are put into a map. The weight should roughly tell how much time does it take to pass through that area. So, lets keep it simple and say we're using tiles. If our character moves half its normal speed in, for example, a jungle, it takes twice as long to pass -> make your weight for that twice as long. If you have diagonal movement, it takes sqrt(2) longer to pass, so you should remember that when weighting diagonal movement. If you're using tilemaps, you can just go over the map and save the weights into an array, if you're using something non-tiley, you should write a tool for handplacing the weights (still, keep them roughly equal to the time it takes, you can actually go walk inside your system and measure times)

I once had a great article about A* in my favourites but it seems it's lost forever

[Sigma]

So in a non tiley environment we have to place some way points and we have to extract data from those when the player is within a range. Im i correct?

[Bob le Moche]

A* in a game that's not tile-based can be considerably more tricky to get to work correctly if you're not careful.
I wrote an article on the subject a while ago:
http://jax.sus.mcgill.ca/~jdespl/mammoth.html
This could help you avoid some of the problems you might encounter. Feel free to tell me if you have any questions!

[Sigma]

then can i divide a non tiley environment into tiles? if so how can i implement in flash say for example?

[cmspice]

I don't know what your programming proficiency, but if you are asking about implementation, you should consider reading up on data structures and trying to program a linked list and then a binary search tree if you have not done so (better yet, take a class). A BST (Binary search tree) will teach you the basics of constructing a graph like data structure and how to traverse it. In application, this graph like data structure can represent a tiled graph of all the places that are accesible. For example, you start in the corner, so your starting node in the graph has a list of pointers to two other nodes representing NORTH and EAST but lets say going NORTH you have to cross a river so the timecost on NORTH is 50 while only 10 on EAST. That should all make a lot more sense if you are familiar with graphs in data structures. The basic implementation of this would be something like

class node
{
int weight = some number
LinkedList<node> roads
function addNode(node)
{roads.add(node)}
*some more methods*
}

just to give you an idea of what your dealing with here.

[raigan]

then can i divide a non tiley environment into tiles? if so how can i implement in flash say for example?

The algorithms you listed (A* and Dijkstra) are applied to a graph, so you need a graph to run them on. A grid (of tiles) is just a specific type of graph, where each tile is a node and each node is connected to four other nodes (i.e adjacent tiles in the graph).

For a non-tile-based world there are other possible approaches to representing the environment as a graph, some of which might be better (e.g more useful, simpler, sparser, more compact, etc.) than a grid of tiles; "waypoint graph" or (increasingly popular) "navigation mesh" are two other types of graph which are commonly used to represent the gameworld for AI/pathfinding that you might want to google for.

[Sigma]

thanks for the reply guys. I will go through the trees first. So far i just used trees for sorting, I will explore how to store a graph in a tree and how to traverse...

[Sigma]

Hi Guys,
      With the help and valuable suggestion of you guys i did path finding in a tile based environment and also using waypoints in a non tile based environment. Everything works fine in waypoint based path finding, the only trouble is how can the AI find its nearest waypoint? can anyone tell me how to find the nearest waypoint? i stored all the waypoints in an array. I don't want to apply distance formula for all waypoints in the array and the enemy AI position to find out the shortest distance, because I think its a processor intensive job to calculate SQRT and again i have to sort out all the values. So kindly give me some other solutions.

Thanks in Advance......

[nikki]

Hi great that youve got some things going,
it's a great feeling to have mastered some -before magic- stuff right 

instead of sqrt you could just add the deltax and deltay of each waypoint , then you wouldn't know exactly how far (in pixels,cm,nm or whatever) the closest waypoint is, but you would know wich waypoint is the closest.

I think you could lower the amount of calculations (better said , not check all waypoints) if you have some kind of division of your world (think tilemap, wich very big tiles) in those tiles there could be one or many waypoints, but you needn't check all waypooints like this. I believe the 'official way' is by using quadtrees i have implemeted them too, and i've never studied no computer science

[Sam]

A very simple trick is to not do the SQRT when calculating distance.  This will mean you wil actually calculate distance², but that's fine as whatever waypoint has the smallest distance will also always have the smallest distance².  Just make sure you're always comparing distance² with distance².

distance = SQRT( (dx * dx) + (dy * dy) )

distance² = (dx * dx) + (dy * dy)

Just adding the differences in X and Y coordinates would not give you a value that you can reliably use for comparing distance.  Consider one waypoint that is at (5,0) and another at (3,3).  Which is closer to (0,0)?  Looking at just the sum of the difference in position, (5,0) would seem to be closer.  Work out the true distance and you find that (3,3) is considerably closer.

[Klaim]

To learn and implement this algorithm in two NDS games (using game-specific optimizations) I used this excellent book that explains very well and step by step and based on examples : http://www.amazon.com/Programming-Game-Example-Mat-Buckland/dp/1556220782

It's a well known book and if you really want to understand how to make game ai, it's really a must have.

[kiwi]

Hmm, I'd suggest using some sort of an adjacency list(basically an array of lists) on this one, though you'd probably have to change your path finding algorithm to fit the new data structure.

So let's say you have a graph like this one
a-b
|\| 
c-d

Your list would look like this then
a -> b -> c -> d
b -> a -> d
c -> a -> d
d -> a -> b -> c
And if you sort the list in an ascending order, then the closest waypoint would be the first element in the list.

[ColossusEntertainment]

because I think its a processor intensive job

It is generally a good practice to not assume things when it comes to performance. Make the simple implementation first (even if you suspect that it might perform poorly) just to get the functionality in there and working. Regularly run your code through a profiler throughout the development, and address things that stand out as problem areas in the profiling results. Usually, it's not going to be the ones you would have guessed.

Why take the time to optimize your adjacency-finding code at this stage, when you don't know if it's going to cause a problem?

[Martin 2BAM]

I don't really have anything helpful to say here so instead I'm just gonna link this article.

I like to point out that the idea on that article is already implemented in UT3/UDK, which is also shown to be buggy in the video; Probably because the pathfinding method isn't taking into account a dynamic mesh placed, the crate, on front of the bot.

Also I suggest the original poster to change the title of the thread to something more specific, to more likely catch the eye of the savvy.

[Sigma]

To learn and implement this algorithm in two NDS games (using game-specific optimizations) I used this excellent book that explains very well and step by step and based on examples : http://www.amazon.com/Programming-Game-Example-Mat-Buckland/dp/1556220782

It's a well known book and if you really want to understand how to make game ai, it's really a must have.

I'm also using the same book but i didn't go through the samples, i think that's the problem. i don't thing closest waypoint is explained in the book.

[Sigma]

Hmm, I'd suggest using some sort of an adjacency list(basically an array of lists) on this one, though you'd probably have to change your path finding algorithm to fit the new data structure.

So let's say you have a graph like this one
a-b
|\| 
c-d

Your list would look like this then
a -> b -> c -> d
b -> a -> d
c -> a -> d
d -> a -> b -> c
And if you sort the list in an ascending order, then the closest waypoint would be the first element in the list.

But if i'm working a relatively huge map with more points i think i will take more time.Is it So?

[kiwi]

Depends on how often those waypoints change, if they're static, then no, you just have to precompute it and because you have an array of lists, any access is done in O(1) time.

If waypoints do change, then at any given frame you have to first sort the list of neighbors and then take the first one, which on average takes O(n logn) time, where n is the number of neighbors you waypoint has.
If you were to make the distance between a given waypoint and every other waypoint in your array, that would be an O(n), but for a much larger n given the fact that you have a big map.

So technically, it should be faster in both cases.