Jump to content
  • Advertisement
Sign in to follow this  
fooman_69

Beginner with A*

This topic is 4876 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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!