quote: Original post by Timkin

(Besides, part of my motivation for encouraging Dijkstra''s was to get people to learn that there is more out there than just A*, neural nets, genetic algorithms and finite state machines! )BR>

I was wondering how many people out there use neural nets or genetic algorithms in their AI work? Maybe I should be more general, can I have a straw poll or what techniques you use in your programming, which ones you''ve tried and discarded and which you have no clue about (or have just never implemented).

Personally I''m heavily into neural nets and genetic algorithms at the moment, having implemented both in testbeds with pretty cool successes. I''ve written tons of finite state machines in the past, used A* and the other breadth first/depth first search methods and unsuccesfully tried to implement an expert system once, but I was young and foolish and ended up with linked lists of pointers to linked lists of pointers to linked lists of tree structures and it all fell apart.

The reason I ask isn''t my wanting to say what I''ve done, but I want to know what you''ve done and why you don''t use certain techniques.

Mike

quote: Original post by MikeD

I was wondering how many people out there use neural nets or genetic algorithms in their AI work? Maybe I should be more general, can I have a straw poll or what techniques you use in your programming, which ones you've tried and discarded and which you have no clue about (or have just never implemented).

Mike

I would be more interested in knowing what people have actually implemented in shipping
commercial computer games. Building a technique to mess around with in a testbed is one
thing, shipping a commercial product with it is something else entirely.

That being asked, in 1987 I used an ANN for strategic decisions in Parachutes at Kanev
which never shipped (publisher went out of business). In 1995 I built a GA for vehicle routing
(not pathfinding) for Enemy Nations but ended up shipping EN without the GA because
the GA was too slow. Since then, the games I've worked on only shipped with A*, FSMs, Fuzzy
Logic and Expert Systems, all highly influenced by Subsumption Architecture (Brooks).

Eric


Edited by - Geta on July 12, 2001 10:01:48 AM

quote: Original post by Timkin
...and that will most likely be due to the difficulty in finding admissable heuristics in non-Euclidean spaces! Did you consider using the metric appropriate to the space as your heuristic unit length?

Cheers,

Tim

I believe we did. This was, however, in 1997 for Rebel Moon Revolution (a FPS that actually
shipped under the title War in Heaven and the developer had changed the game to the point
where the non-Euclidean geometry aspect went away, so the Dijkstra''s code never got called after
the game shipped.) Anyway, I have had 6 other game projects and 6-7 testbeds since, so I''m
not exactly sure how I implemented the Dijkstra''s at this time. I just recall that it worked better
than the A* did for solving the problem we had to solve.

Doesn''t Dijkstra''s process DFS anyway?

Eric

quote: Original post by Geta
Doesn''t Dijkstra''s process DFS anyway?

Okay, time to admit I goofed yesterday... don''t know where my brain went. You were correct in stating that omitting the heuristic cost forces A* to act as uniform cost search (for which Dijkstra''s algorithm is (under certain conditions) an optimal algorithm). The primary difference between uniform cost search vs depth first search is that depth first will always continue expanding the current subtree until it finds a non-goal leaf node. Uniform cost however will always expand the lowest cost leaf node (as measured by the path cost g()). It is obvious then that A* reverts to uniform cost when the heuristic omitted.

My apologies for the error.

Cheers,

Tim

quote: Original post by Timkin

Okay, time to admit I goofed yesterday... don't know where my brain went. You were correct in stating that omitting the heuristic cost forces A* to act as uniform cost search (for which Dijkstra's algorithm is (under certain conditions) an optimal algorithm). The primary difference between uniform cost search vs depth first search is that depth first will always continue expanding the current subtree until it finds a non-goal leaf node. Uniform cost however will always expand the lowest cost leaf node (as measured by the path cost g()). It is obvious then that A* reverts to uniform cost when the heuristic omitted.

My apologies for the error.

Cheers,

Tim

Hey, no problem. I count on making several each day myself!

Just find 'em, fix 'em and move on. (thankfully, no one is really keeping score)

Eric


Edited by - Geta on July 13, 2001 9:29:42 AM

I worked for a year on the PC/Dreamcast version of "America''s Scariest Police Chases", which got canned and our company folded so it wasn''t released, but it''s my only point of view so here goes.
I used FSM, fuzzy logic and A* for the various AI tasks in the game. One point where I would have augmented this is the optimisation of the heuristics for things like lane choice for cars in the game. There were about 15 factors in deciding which lane to be in which were constantly being tweaked this way and that to get certain styles of behaviour for different vehicles. I''d definately have liked to have used GA''s to optimise the heuristics for these behaviours, to ensure cars were in the right lanes to turn corners, not crash into other cars etc...

Btw, I''m not sure how many people are professionals here, so please, any opinions welcome as always.

Mike