Beginner with A*
Author
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.
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
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
Author
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??
Priority queues order inserts according to some property of the inserted elements, rather than in order of insertion.
Author
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??
'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.
Author
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?
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).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
