Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (477)
Games in Android Showcase (106)
games submitted by our members
Games in WIP (533)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Pathfinding, and your A* Heuristic of choice?  (Read 1953 times)
0 Members and 1 Guest are viewing this topic.
Offline heisenbergman

JGO Coder


Medals: 14


L___ o_ G___ a__ P___


« Posted 2013-06-10 09: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

Offline MatthewNicholls

Junior Member


Medals: 1
Exp: 6 years



« Reply #1 - Posted 2013-06-10 10: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  Grin

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

JGO Coder


Medals: 14


L___ o_ G___ a__ P___


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

Ill just try implementing the Manhattan method first Tongue

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline MatthewNicholls

Junior Member


Medals: 1
Exp: 6 years



« Reply #3 - Posted 2013-06-10 15: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!"
Offline heisenbergman

JGO Coder


Medals: 14


L___ o_ G___ a__ P___


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

Programming AI is kicking my ass Tongue 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.

Offline MatthewNicholls

Junior Member


Medals: 1
Exp: 6 years



« Reply #5 - Posted 2013-06-13 10: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!"
Offline heisenbergman

JGO Coder


Medals: 14


L___ o_ G___ a__ P___


« Reply #6 - Posted 2013-06-13 11: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 Tongue

(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)

Offline heisenbergman

JGO Coder


Medals: 14


L___ o_ G___ a__ P___


« Reply #7 - Posted 2013-06-13 11: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.

pw (26 views)
2014-07-24 01:59:36

Riven (25 views)
2014-07-23 21:16:32

Riven (20 views)
2014-07-23 21:07:15

Riven (22 views)
2014-07-23 20:56:16

ctomni231 (51 views)
2014-07-18 06:55:21

Zero Volt (46 views)
2014-07-17 23:47:54

danieldean (37 views)
2014-07-17 23:41:23

MustardPeter (40 views)
2014-07-16 23:30:00

Cero (56 views)
2014-07-16 00:42:17

Riven (55 views)
2014-07-14 18:02:53
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!