New to AI Programming

[steved3298]

Hi,
I am creating a new 2D game using the Ruby programming language and have finally got around to trying to add Bots and AI to my game. Sadly, I have never had experience with programming bots and was wondering if anyone could refer me some very basic code that I could read through (or articles). I have read most of the articles from the Resources thread in this forum, but I haven't been able to pick much up from the articles.

Thanks,
Steve

[Brainz]

You could try the wiki...

[mirv]

I'm no bot programmer myself (only did half a year in a.i theory) but as a programmer nothing beats experience and getting your hands dirty. So I'd recommend getting something to move around in an intelligent manner first - A* searches seem the current popular method.
And books may be the way to go if you find stuff on the Internet unsuitable.
Any more experienced bot guys & girls feel free to shoot me down in flames.

[steved3298]

I have been thinking about doing a simple or robust trace because it seems fairly easy to implement and is good for learning, but I haven't been able find anything but a description of how it works and I was wondering if anyone could point me to a code example (whatever language works).

[steved3298]

Alrighty. So I have implemented the A* Algorithm into Ruby from a couple C++ and Python examples but as of right now I am getting incredibly slow performance. It takes over 5(!) seconds to find a path from a point to another (~600 pixels away). The code is at http://www.nebulargauntlet.org/trac/...k/lib/astar.rb if someone who is more experienced could maybe comment a little?

Thanks,
Steven D.

[@$3.1415rin]

A* on a 600x600 mesh is slow, especially if there is no valid path. in current cstrike bots we talk about A* on graphs with usually <4000-8000 nodes

I wrote a bit about my A* implementation on http://www.lampel.net/johannes/joebo...XPDoc-beta.pdf
maybe that helps a bit

[DrEvil]

Shouldn't be that slow. Implementing A* in a scripting language is the first problem. Scripting languages aren't well suited for graph searches, or any other high cost calculations for that matter. If you are embedding into a lower level app like c++ I'd recommend doing tha A* in there, and exposing functions to do searches. If that isn't an option(the whole app in script?), some things you can do are:

1) Use better data structures. Looks like you brute force your search in functions like get_best_open_node. That is usually implemented in a priority queue.
2) Pre-process your map into a lower resolution search space. This will likely be what gives you the best speedup. Merge large areas of pixels into axis aligned or convex shapes. Then you just A* using those areas instead of pixels.

Bottom of this link describes a method that should work well for you:
http://www.gamasutra.com/features/20020405/smith_01.htm

I'm doing something very similar with my bot in 3d.
http://www.omni-bot.de/e107/e107_plu...topic.php?4142

First flooding the level with small nodes, then merging into sectors that will then be used for navigation. This would be much easier in 2d even.

Also if your environment is pretty static you could pre-process a lookup table using floyd-warshall, resulting in about a ~1.3M(or700k if you used shorts, but most scripting languages dont have many options for that) lookup table.

There's many options, but the first thing I'd do is move the search out of script if possible, change your data structures, then if performance still isnt acceptable a hierarchial pre-processing is probably the next easiest step, the point there being to greatly reduce the search space.

Since it sounds like you are bound completely in the scripting language reducing the search space and optimizing your data structures are your main options.

[steved3298]

Thanks for your replies. In response to DrEvil, I was wondering if there is some sort of algorithm for generating regions and if not maybe how one would go about implementing it (I get the general idea, but am totally clueless on details such as region size, etc.). I also implemented a C-based Priority Queue and it did speed up the search a little but not too much more. I think the regions/sectors idea will probably work, so if you could just give me a slight push in the right direction (maybe even a small code sample) it would help me immensely. Thanks guys.

[steved3298]

Alright, I implemented Tiles to cover the map and make searching much easier. It is much faster than before (On my test, from 6seconds, to just over a second). I will also try to implement the priority-queue (I found a C-based version) and hopefully gain some more performance there. For the tiles I am using 16x16 pixels and I was just wondering if that is a valid square or should they be larger (the map is 1024x1024)?

Thanks for the suggestions.

[steved3298]

Alright, not searching for diagonal paths (which I'm pretty sure I implemented wrong anyway) decreases the search time incredibly from before (from over 1 sec to ~30ms).

EDIT: Fixed diagonal searching, seems my H heuristic was completely off and was sending the A* search in every possible tile between the points. Still faster with H fixed.