• Advertisement
Sign in to follow this  

Beginner with A*

This topic is 4782 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

hello, I am fairly new to game programming and have done a simple maze game using ascii-characters and need to get the monster's to follow my player. I have read up on the A* algorithm quite a bit and am getting to know it fairly well, however I have a few questions about the list What kind of list is best to use for the Open and Closed lists?? I was going to use vectors, but when I need to remove the first item in the list I would need to reorder it... which is kind of time-consuming isn't it? Considering I would just be sorting it later once more nodes get added to the list... Also, since I already have the game area all set-up before calling any of these methods, should I just pass in the size of the area to initialize these lists? Excuse me if I am expressing stupidity... I am at my wits end for the day and would love any kind of feedback.

Share this post


Link to post
Share on other sites
Advertisement
For most applications of A* a priority queue of some type is the best way to go.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
A simple question, what is the best programming language to implement AI?

Share this post


Link to post
Share on other sites
Lisp.

Its list handeling abilities make it really easy to implement ai.
It can be tough learning tho.

Any other heigh level language would work, but lisp is the best.

From,
Nice coder

Share this post


Link to post
Share on other sites
Quote:
Original post by fup
For most applications of A* a priority queue of some type is the best way to go.


what is the different between a queue and a priority queue??

Share this post


Link to post
Share on other sites
Priority queues order inserts according to some property of the inserted elements, rather than in order of insertion.

Share this post


Link to post
Share on other sites
But in many A* tutorials I read, you have to check nodes against those already in the open list. Therefore, a priority_queue is not good because you can't iterate through it. Am I just misunderstanding the articles I read??

Share this post


Link to post
Share on other sites
'Priority queue' is not the same as 'std::priority_queue'. The first is a general term, the second is a specific implementation which I find largely useless. You could consider using an std::map as a priority queue, and you can iterate over that.

Share this post


Link to post
Share on other sites
Quote:
Original post by Kylotan
'Priority queue' is not the same as 'std::priority_queue'. The first is a general term, the second is a specific implementation which I find largely useless. You could consider using an std::map as a priority queue, and you can iterate over that.


I will look into the std::map!
Can you define basic uses for it?

Share this post


Link to post
Share on other sites
Don't use std::map. It's not possible to use it if you have nodes that evaluate to the same value in your heuristic. To overcome this, either use std::multimap or std::push_heap and std::pop_heap together with an underlying container of your choice (e.g. a vector or a list).

Share this post


Link to post
Share on other sites
Or, just write your own fast priority cue object. It's a fairly trivial excercise.

Timkin

Share this post


Link to post
Share on other sites
For the checking of nodes, couldn't you use a binary search tree for that?

You go and insert each node, into the bst, (at o(log2 n) time), and when searching for a node, you simply look at the bst, and find the node, in o(log2 n) time.

That would be mighty fast, and mighty easy to make.

A link

For the actual Que (the open list).
Thats a hard one.

You basically looking for the minimum, in a list.

What you could do, is you have a vector of a struct.
In that struct, you have a pointer to a node, and a value.

Now, when you update a node, you go and shove all of its sucessors onto the End of the vector.

You then search the vector, from the end to the beginning. And then compare and pick, until you find the minimum one.

This is better then the sort and pick, which averages o(n log2 n).
This would be o(n) Which is very useful.

There should be a better way.

You could make up a binary tree, and as your going, you insert each and every node that you have into it.

Its then only o(log2 n) retrieval, and o(log2 n) insertion. So it'd be pretty fast.

And as an added bonus, you could check if a node is already there, as you insert it. So that there are no circular paths.

From,
Nice coder

Share this post


Link to post
Share on other sites
I expect that sorted insertions into a list can be done reasonably efficiently with a simple linked list. In theory every insertion is going to be O(N), but in practice you have a lot of coherence from one insertion to the next and you can take advantage of this.

eg. In a grid-based game, 1 node examined has 8 neighbours to put on the open list. They will tend to have very similar values due to their proximity. So you can cut down the amount of open list you have to search through by starting from the insert position of the last node, instead of the start of the list.

The simplicity of implementing this may turn out to give you significant benefits compared to using a tree.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I would say for that a Binary Tree would be much better!
Enqueue-> O( lgn )
Dequeue-> O( lgn )
(note that lgn grows very very much more slowly compared to O(n) )

I tried both a sorted queue and a binary tree, and the tree version wins totally! Especially if u have got many nodes. Maybe better to write yur own tree, maybe inplementing a lax AVL tree...

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement