GameDev.net Posting Guidelines (please read before posting)
Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.
Posted 07 November 2012 - 10:44 AM
Posted 07 November 2012 - 11:03 AM
I'd say it's exactly like the travelling salesman problem, if the only purpose is to decrease
Time_Spent / Goodies_CollectedIt's still interesting, though.
-Are there obstacles involved?
Posted 07 November 2012 - 11:29 AM
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI
Posted 07 November 2012 - 12:14 PM
It is, indeed, the Traveling Salesman Problem. Welcome to the world of NP-Hard.
However, remember that you don't need to actually solve TSP to get your agents to look good. There are a number of ways you can go about it so that they look reasonable without being mathematically purely rational.
The most obvious way of doing it is by simply moving to the closest one at any given time. When you reach it, move to the closest one from that point. That does make for some edge cases that are really stupid, however. Imagine that one bullet is 10 west of your position and ALL the rest of the bullets are 11 east of your position. The "nearest" algorithm will move to the single west one first and then backtrack (21 spaces!) east to the rest of them. This is obviously not optimal.
Another (much better) solution is to use multi-layered influence maps that combine the locations of bullets with your own location. That combines "where is the stuff?" with "what is closest to me?" Each bullet would radiate out a decaying influence map onto the world. By adding up all those influences, you will get a "heat map" that shows where the biggest clusters of bullets are. The problem is, if you move towards that area, you might bypass "targets of opportunity" on the way. (for example, bypassing a single bullet at 5 east to get to the cluster at 15 east). However, if you also overlay information radiating out from your current position, you are adding in the part that says "and is close to me". Therefore, on your way to that cluster at 15 east, you will pass by the one at 5 east and take advantage of it simply because it is being combined with the fact that it is close to you. This approach will result in behavior that looks a lot more like how humans process the problem and, therefore, will look natural to us. It may not be perfectly mathematical... but neither are we.
Sorry I don't have time to make pretty pictures for you. Hope it made sense in text.
Posted 07 November 2012 - 12:43 PM
Posted 07 November 2012 - 06:55 PM
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI
Posted 13 November 2012 - 03:51 PM
Edited by Icebone1000, 13 November 2012 - 03:55 PM.
Posted 13 November 2012 - 05:03 PM
Posted 13 November 2012 - 07:53 PM
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI
Posted 15 November 2012 - 10:50 AM
Second, its a question about BFS (not much an AI topic itself), theres any way to keep track of the steps without storing it in each node added to the open list, but on the algorithm itself?
Edited by CuriosityKills, 15 November 2012 - 10:58 AM.
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.
GameDev.net™, the GameDev.net logo, and GDNet™ are trademarks of GameDev.net, LLC.