Java-Gaming.org Hi !
 Featured games (83) games approved by the League of Dukes Games in Showcase (523) Games in Android Showcase (127) games submitted by our members Games in WIP (591) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Pathfinding, and your A* Heuristic of choice?  (Read 2353 times) 0 Members and 1 Guest are viewing this topic.
heisenbergman

JGO Coder

Medals: 14

L___ o_ G___ a__ P___

 « Posted 2013-06-10 07:29:19 »

I've just gotten to the point in my game that I need to tweak my enemy AI, which has led me to research pathfinding and subsequently A* and its heuristics.

I find it really fascinating, which leads me to wonder what other game devs think about the different heuristics used for this purpose.

So far I've come across the Manhattan, Diagonal and Euclidean methods and I can't wait to try and implement this in my game.

Do you have a personal favorite heuristic method?

P.S. - These tutorials have been great reads:

A* Pathfinding for Beginners
Heuristics and A* Pathfinding
A*’s Use of the Heuristic

MatthewNicholls

Junior Devvie

Medals: 6
Exp: 6 years

 « Reply #1 - Posted 2013-06-10 08:44:12 »

I haven't implemented any AI yet, but from extensive testing during my degree course on AI it seams like the Heuristic of choice is the one that fits the job at the time. The problem is there isn't a fits all heuristic, you have to test and see what works with what you are trying to do. So my heuristic of choice is the one that fits the job

my blog
"...Muahahhah.ahahah... pull the lever Egor!" ..."Yesh mashter"..click... click...click..buzzzzz".......Its Alive!"
heisenbergman

JGO Coder

Medals: 14

L___ o_ G___ a__ P___

 « Reply #2 - Posted 2013-06-10 09:11:23 »

Ill just try implementing the Manhattan method first

MatthewNicholls

Junior Devvie

Medals: 6
Exp: 6 years

 « Reply #3 - Posted 2013-06-10 13:59:20 »

Here are some quotes of my findings from one of my Assignments from the course with the open university 'Natural and Artificial Intelligence'.

context : search in Sokoban ( a puzzle game)
Quote
"One method of developing heuristics is to identify constraints in the problem and relax them to form an easier problem. The cost of solving the easier problem can be quickly calculated; which gives an approximate cost for solving the real problem...."

Quote
How many constraints you relax to develop a heuristic depends on the complexity of the task and the time it takes to evaluate. Relaxing one might be enough to create the most efficient heuristic or you might need two or more, but there is a balance that needs to be met so that the best heuristic is found within the allotted development time. Bringing in too much complexity can lead to confusing and unmanageable code. However exploring a number of constraints can lead to a better solution.
The best heuristic is the one which more accurately estimates the cost and so more accurately guides the search towards the goal state, resulting in fewer nodes expanded which means a faster and optimal search. The heuristic should also be admissible.

Quote
A heuristic is admissible if it always underestimates the cost of the path to the solution. It is important for finding optimal solutions at it means the partially constructed optimal paths will always be chosen over the sub optimal paths to the goal state.

Quote
The things that affect the relative performance of the algorithms using different heuristics appear to be the size of the state space, if it is small then a less complex algorithm can find it fast. If the state space is large then the similar algorithm that is slightly less complex can be faster but expands more nodes. So I if you had to choose only one algorithm/ heuristic it would be best to use A* (displaced heuristic) as it is complete optimal and efficient.....

Obviously my results are only valid for the Sokoban puzzle that i was experimenting with but there are some general principles to draw from.
We used a program called 'search lab' which let you try out many different combinations of algorithms.

my blog
"...Muahahhah.ahahah... pull the lever Egor!" ..."Yesh mashter"..click... click...click..buzzzzz".......Its Alive!"
heisenbergman

JGO Coder

Medals: 14

L___ o_ G___ a__ P___

 « Reply #4 - Posted 2013-06-13 06:16:40 »

Programming AI is kicking my ass Spent the last two days tweaking my enemy AI to follow a path towards the player and avoid any obstacles it may encounter.

I'm getting there using A*, but there are still occassions where I'm not liking how my enemies move, so I'll have to continue tweaking.

I must say, doing this has been a pain, but utterly fascinating.

MatthewNicholls

Junior Devvie

Medals: 6
Exp: 6 years

 « Reply #5 - Posted 2013-06-13 08:45:47 »

The AI part of my game engine is the part I'm most looking forward to. I really enjoyed studying it so I'm hoping it wont take to long to get started on.

So how does your AI work, are they free roaming or stuck on a grid of nodes?

my blog
"...Muahahhah.ahahah... pull the lever Egor!" ..."Yesh mashter"..click... click...click..buzzzzz".......Its Alive!"
heisenbergman

JGO Coder

Medals: 14

L___ o_ G___ a__ P___

 « Reply #6 - Posted 2013-06-13 09:02:08 »

I divided my game area into a grid of nodes and the general logic follows pretty much the "A* Pathfinding for Beginners" tutorial (I used the Manhattan Method as my heuristic).

Most of the logic I had to figure out was how to check for nodes that can't be traversed due to containing obstacles and such; but since I'm using Box2D, I did this via QueryAABB and RayCast.

It has all worked fine so far and has come quite a long way since I started with my primitive logic although there are some situations where the enemies in the game still don't act realistically enough. I already have some fixes in mind, which I hope to implement soon when I find time.

So far this has been the most challenging and interesting aspect of learning how to develop games thus far

(EDIT: Although I should probably use the Euclidean distance heuristic since my game is not actually divided into grids and the objects can move in fractional increments in any direction)

heisenbergman

JGO Coder

Medals: 14

L___ o_ G___ a__ P___

 « Reply #7 - Posted 2013-06-13 09:15:58 »

There's this new algorithm I came across called a Jump Point Search btw.

I haven't yet absorbed it all though:

http://harablog.wordpress.com/2011/09/07/jump-point-search/

Pages: [1]
 ignore  |  Print

You cannot reply to this message, because it is very, very old.

 Add your game by posting it in the WIP section, or publish it in Showcase. The first screenshot will be displayed as a thumbnail.
 Gibbo3771 (7 views) 2014-11-24 22:59:16 trollwarrior1 (35 views) 2014-11-22 15:13:56 xFryIx (73 views) 2014-11-13 15:34:49 digdugdiggy (52 views) 2014-11-13 00:11:50 digdugdiggy (46 views) 2014-11-13 00:10:15 digdugdiggy (40 views) 2014-11-13 00:09:33 kovacsa (66 views) 2014-11-07 22:57:14 TehJavaDev (70 views) 2014-11-04 01:04:50 BurntPizza (68 views) 2014-11-03 21:54:52 moogie (83 views) 2014-11-03 09:22:04
 basil_ 29x theagentd 28x HeroesGraveDev 25x BurntPizza 20x Spasi 19x Riven 18x KevinWorkman 15x princec 13x SHC 12x Gibbo3771 11x gouessej 11x CopyableCougar4 10x kevglass 10x kpars 10x LiquidNitrogen 10x Longarmx 9x
 Understanding relations between setOrigin, setScale and setPosition in libGdx2014-10-09 22:35:00Definite guide to supporting multiple device resolutions on Android (2014)2014-10-02 22:36:02List of Learning Resources2014-08-16 10:40:00List of Learning Resources2014-08-05 19:33:27Resources for WIP games2014-08-01 16:20:17Resources for WIP games2014-08-01 16:19:50List of Learning Resources2014-07-31 16:29:50List of Learning Resources2014-07-31 16:26:06
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org