• 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.

Yanroy

Weird Pathfinding AI

3 posts in this topic

For my MUD, I need a way to make the NPCs follow people and seek them. I would use the A* algorithm, but I have a somewhat unique problem (I think...) Instead of having places on the map where you can't walk (i.e. rocks, water, anything else impassible), I don't have anything there. Look at this example (x indicates where there is a map square, ' ' is just dead space NOT empty array elements because there isn't any array): x x x xxxxxxxxxxxxxxxxxxxxxxxx x        x x        x x        x I hope you can see the problem here. If I have an NPC in the lower left corner, and there is an enemy (human) on that spoke sticking out of the top, how do I make the NPC find the path to the human? There is no array to use the A* algorithm on. I can't determine whether it is even north or south without trying all possible paths! I know this can be fixed... other MUDs have done it. Just noticed a couple of errors in the post Edited by - Yanroy on 5/4/00 7:35:07 AM
0

Share this post


Link to post
Share on other sites
Actually the A* algorithm is defined to work with nodes, not array elements. In your case the x:es in your drawing is your node. Each node must have knowledge of the nodes they are connected to. Then as the A* algorithm visits a node it adds the nodes neighbours to the next possible nodes.

The A* star algorithm doesn''t need to know which direction is north, all it cares about is the cost for walking to where it is and the cost it has left to the goal. Of course it doesn''t know the cost left so it has to guess. You need to have some way of guessing the distance between two nodes, I would suggest comparing their coordinates. If the nodes have absolutely no idea where they are relative each other the A* must guess that the cost left is zero. That way it will search in an expanding circle around the start until it reaches the goal.

I hope I made any sense amidst my ramblings.

- WitchLord
0

Share this post


Link to post
Share on other sites
I suppose I should have said this before.... In order to get the cost of going to a specific place, I need to run the A* algorithm, which needs a cost.... I didn''t know you could use a constant cost. The other thing is, there aren''t any coordinates whatsoever. In fact, different groups of nodes don''t even know other groups exist. It is extreemly compartmentalized (that is usually good, right? ) The reason for that is I have a MUD namespace, containing, among other things, a list of Areas, which in turn contain lists of Locations, which contain lists of players and items. All the Locations in one Area are connected to each other, but the Area itself forms the bridge from the inside Locations to the Locations of an adjacent Area. (btw, the Area''s are only adjacent in the sense they are connected to each other). I will see if I can work A* into this...

--------------------


You are not a real programmer until you end all your sentences with semicolons;

Yanroy@usa.com

Visit the ROAD Programming Website for more programming help.

0

Share this post


Link to post
Share on other sites
Ah, you mean to say that you don''t know how to formulate a good heuristic since the space is not necessarily 2D An A* search without the heuristic is essentially just a ''breadth-first'' search, I believe, as you have no way of knowing which is the best node except for how far you have already travelled.

Let''s look at this slightly differently. Try calculating in advance which Areas are linked to other areas. Then your first job is to plot the list of areas from the start area to the finish area: this should be really quick, even with something like breadth-first search.

Once you have that list, you just need to
(a) plot the path from the start room to the room with the exit to the 2nd area on the list
(b) plot paths through each area to the exit to the following area
(c) plot a path from the entry to the last area to the target.

This way, you have essentially reduced the number of nodes you need to search to just the relevant areas. If you manage to search an entire area without finding a path from one external link to the other, you probably have a weird area setup, which could be a problem

Personally I wouldn''t try and work the A* heuristic into this, as it''s not really suited to this task, since your rooms and areas are not necessarily linked in any logical way. Most MUDs with the tracking skill just use a simple depth-first search without the area-based optimisation I detailed above.
0

Share this post


Link to post
Share on other sites