• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.

Archived

This topic is now archived and is closed to further replies.

BeanDog

Simple (not really) Pathfinding (yes, again)

30 posts in this topic

quote:
Original post by Kylotan

[quote] Original post by Geta

And for anyone who happens to develop in MSVC++ or Metroworks, I might suggest that you look into using the Standard Template Library (STL) queue container class for a priority queue. I modified it to be a pathing queue by just adding support for iterators (very easy to do) to the queue class object. It has turned out to be blazingly fast, and extremely easy to work with, as an OPEN list.

Eric
(end of Original post by Geta)

What do you mean, added support for iterators? I keep redoing my pathfinding as I can never seem to get a good balance between clean code and good speed


Are you familiar with the STL container classes?

If so, then you should know what iterators are, and that the STL queue container class does not support them. I derived a pathqueue container class from the STL queue class and modified the pathgueue container to support iterators.

If not, then you may want to read a tutorial book on the STL or search the web for an online tutorial. STL comes with MSVC++ and the Metrowerks Codewarrior compiler dev studios (and probably other compilers too) and is well worth learning about.

Eric
0

Share this post


Link to post
Share on other sites
BeanDog, didn''t you read the posts on your last thread? If you divide that 1/20 of a second for many frames, your game doesn''t stop or slow down even if you move tens of units simultaneously. The only problem is that the units you''re trying to move, start moving a bit later than you actually click the screen. But it really doesn''t matter at all.

As far as I recall, it took some time for units to start moving even in C&C and Red Alert. And probably in Starcraft, too. Everyone is dividing AI routines into many frames.

And the search algo I think is used in C&C and Red Alert, is the Best First. This is just like A* but you always move the node that is closest to the goal (which one is closest, is approximated by simple airway- distance to the goal). Best First is actually really fast and it produces reasonable routes.

ps. I sent that region search idea

-Hans
0

Share this post


Link to post
Share on other sites
quote:
Original post by Geta

Are you familiar with the STL container classes?

If so, then you should know what iterators are, and that the STL queue container class does not support them. I derived a pathqueue container class from the STL queue class and modified the pathgueue container to support iterators.


I thought that queue was technically just an adaptor for the deque class? And therefore if you needed iterator access, why not just use the deque anyway? I was more interested in how you used the iterators, as I pretty much just add things to the queue and pop them off the front. Why do you need iterator access to the queue? I guess I''m just asking for a little more algorithmic detail here

In fact, isn''t there a dedicated priority_queue adaptor in the STL? For some reason I couldn''t use it for my A* implementation - I think it was the problem of needing to be able to delete from the inside, which could be why you use iterators?
0

Share this post


Link to post
Share on other sites
quote:
Original post by Kylotan

I thought that queue was technically just an adaptor for the deque class? And therefore if you needed iterator access, why not just use the deque anyway? I was more interested in how you used the iterators, as I pretty much just add things to the queue and pop them off the front. Why do you need iterator access to the queue? I guess I'm just asking for a little more algorithmic detail here

In fact, isn't there a dedicated priority_queue adaptor in the STL? For some reason I couldn't use it for my A* implementation - I think it was the problem of needing to be able to delete from the inside, which could be why you use iterators?


deque and queue are actually separate classes in STL. From what I know, queue is not just an adapter for the deque class, as it can be used with any other container class.

Iterator access to the open list (my pathqueue) was needed for
deletions from the inside of the list.

I forget exactly why I chose not to use the priority_queue adapter (this decision was made in 1997) and instead I choose to modify the queue. My guess would be, that I looked at the source code of both, and I felt that it was easier to modify the queue to do what I wanted, than to use the priority_queue adapter.

Eric


Edited by - Geta on June 22, 2000 9:23:16 AM
0

Share this post


Link to post
Share on other sites
Yes, I believe the priority_queue adapter inhibits access to any element except the top one, so modification of the open list (as A* requires) is not so practical with that implementation.

Out of interest, what data structure do you use for your closed list? I think I use some sort of mapped-bitset (just a minimal-storage hash table, I guess), but I don''t recall if that is actually in my A* implementation. (I have a few different pathfinding algorithms implemented and I''m not at my home computer )
0

Share this post


Link to post
Share on other sites
quote:
Original post by Kylotan

Yes, I believe the priority_queue adapter inhibits access to any element except the top one, so modification of the open list (as A* requires) is not so practical with that implementation.

Out of interest, what data structure do you use for your closed list? I think I use some sort of mapped-bitset (just a minimal-storage hash table, I guess), but I don't recall if that is actually in my A* implementation. (I have a few different pathfinding algorithms implemented and I'm not at my home computer )


I have used both the STL list and the STL map containers for CLOSE list implementations. I think they are about the same in performance in their role as CLOSE lists. They both can rely on the actual NODE pointer address that is stored, as a key value, for identification purposes, so non-contiguous x,y,z nodes can be supported.

Eric


Edited by - Geta on June 23, 2000 9:22:25 AM
0

Share this post


Link to post
Share on other sites