• 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.
Sign in to follow this  
Followers 0
ater1980

Penalized/Constrained Distance Function

10 posts in this topic

Assume a character is located on a n by n grid and has to reach a certain entry on that grid. Its current position is (x1,y1). Also on the same grid is an enemy with coordinates (x2,y2). Each step algorithm randomly generates new candidate locations for the hero (if there are k candidates then there is a kx2 matrix of new potential locations.

What I need is some distance objective function to compare the candidates. I'm currently using d1 - c * d2, where d1 is distance to the objective (measure in terms of number of pixels for each axis), d2 is distance to the enemy and c is some coefficient (this is very much like a set-up for Lagrangian). It's not working very well though. I'd be quite keen to learn how what constrained distance function are used for similar cases.

Any suggestions or references to articles are very much appreciated.
0

Share this post


Link to post
Share on other sites
There's a couple of options that come to mind right off the bat.

One is to separate pathfinding from local navigation, and use something like a steering system with an avoidance force to accomplish your enemy dodging.

The other would be to generate an influence map of the enemy's location and do a gentle falloff of his influence value in the surrounding grid squares, probably using a 1/distance-squared basis function. Then simply add the score of the enemy's influence map values on the grid to the pathfinding cost of each grid tile during A*, and you'll automatically dodge the areas where the enemy is located.

Best part of the second approach is that you can add dozens of enemies to dodge into a single influence map and avoid all of them for the same computational cost during pathing.
-1

Share this post


Link to post
Share on other sites
@Apoch: I thought of mentioning influence maps, but they seem much less useful when using the "pick x random locations" approach to navigation as opposed to A*. Calculating the influence map would dwarf selecting a location if you only consider a handful of locations each frame and enemies can move.

I do definitely agree that enemy influence needs to drop off. Many functions that are asymptotic to zero would be fine, because otherwise the weights of a few enemies [i]anywhere on the map[/i] could totally overwhelm the goal-seeking behaviour.

Lastly I would suggest reconsidering using a better pathfinding method unless there's a good reason. Imagine this scenario:
- Goal G is at (0,0).
- Enemy E1 is at (50,0).
- Enemy E2 is at (0,50).
- Player P is at (50,50).

For values of c >= 0.5, P will almost never reach G, instead being repelled by E1 and E2. In fact the same applies if P starts anywhere on the map outside the triangle G, E1, E2. You may think that tweaking the value of c will fix the problem, but if you keep adding enemies it will break again.
0

Share this post


Link to post
Share on other sites
[quote name='jefferytitan' timestamp='1333957488' post='4929482']
I have to ask... why generate candidates randomly? It's an unusual approach to pathfinding.
[/quote]

Simple evolutionary algorithm. A number of candiate solutions are generated base on the current one. Next step is to attach a fitness/objective function to each of them and then derive probability distribution. The second step is a clincher for me since I don't know how to do find this fitness function. Currently I'm just using d1-c*d2, which I guess is a pretty rough way of doing it.
0

Share this post


Link to post
Share on other sites
[quote name='jefferytitan' timestamp='1334032474' post='4929766']
@Apoch: I thought of mentioning influence maps, but they seem much less useful when using the "pick x random locations" approach to navigation as opposed to A*. Calculating the influence map would dwarf selecting a location if you only consider a handful of locations each frame and enemies can move.

I do definitely agree that enemy influence needs to drop off. Many functions that are asymptotic to zero would be fine, because otherwise the weights of a few enemies [i]anywhere on the map[/i] could totally overwhelm the goal-seeking behaviour.

Lastly I would suggest reconsidering using a better pathfinding method unless there's a good reason. Imagine this scenario:
- Goal G is at (0,0).
- Enemy E1 is at (50,0).
- Enemy E2 is at (0,50).
- Player P is at (50,50).

For values of c >= 0.5, P will almost never reach G, instead being repelled by E1 and E2. In fact the same applies if P starts anywhere on the map outside the triangle G, E1, E2. You may think that tweaking the value of c will fix the problem, but if you keep adding enemies it will break again.
[/quote]

what you say makes sense, but honestly it's not my impression: for c<1 P pretty much ignores enemies regardless of the distance to them(or so far I haven't noticed much strategy in the trajectory), but for c>1 it just stays in one spot for a long time scared to death by them. I'm quite sure there should be some systematic way people design these ditance functions.
0

Share this post


Link to post
Share on other sites
I'm really honestly puzzled as to why you're using an evolutionary algorithm for pathing, when pathing is a very well understood problem with a number of extremely good solutions.

It kind of strikes me as similar to using a sandwich to hammer in nails. If you're incredibly patient and have really cooperative nails, you might get somewhere before you die of old age... but it seems to me like you should trade the sandwich for a hammer and just get the job done.
0

Share this post


Link to post
Share on other sites
[quote name='ApochPiQ' timestamp='1334080058' post='4929954']
I'm really honestly puzzled as to why you're using an evolutionary algorithm for pathing, when pathing is a very well understood problem with a number of extremely good solutions.

It kind of strikes me as similar to using a sandwich to hammer in nails. If you're incredibly patient and have really cooperative nails, you might get somewhere before you die of old age... but it seems to me like you should trade the sandwich for a hammer and just get the job done.
[/quote]

Can you suggest some articles or manuals on this topic? I really have never done this before.
0

Share this post


Link to post
Share on other sites
[quote name='ApochPiQ' timestamp='1334130956' post='4930168']
You should probably start with [url="http://en.wikipedia.org/wiki/A*_search_algorithm"]A*[/url].
[/quote]

Ok thanks. Does it work if enemies perform eandom walk on the grid?
-1

Share this post


Link to post
Share on other sites
If your obstacles are moving, you probably also want to look into [i]steering systeems[/i], particularly the canonical "Boids" demo by Craig Reynolds.
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0