.:: Bots United ::.  
filebase forums discord server github wiki web
cubebot epodbot fritzbot gravebot grogbot hpbbot ivpbot jkbotti joebot
meanmod podbotmm racc rcbot realbot sandbot shrikebot soulfathermaps yapb

Go Back   .:: Bots United ::. > Developer's Farm > General Bot Coding
General Bot Coding See what a pain it is to get those little mechs shooting around

Reply
 
Thread Tools
New to AI Programming
Old
  (#1)
steved3298
Member
 
steved3298's Avatar
 
Status: Offline
Posts: 6
Join Date: Sep 2006
Default New to AI Programming - 06-09-2006

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
  
Reply With Quote
Re: New to AI Programming
Old
  (#2)
Brainz
Member
 
Brainz's Avatar
 
Status: Offline
Posts: 270
Join Date: Jun 2004
Location: Nottingham, UK
Default Re: New to AI Programming - 06-09-2006

You could try the wiki...
  
Reply With Quote
Re: New to AI Programming
Old
  (#3)
mirv
Super Moderator
 
mirv's Avatar
 
Status: Offline
Posts: 152
Join Date: Apr 2004
Default Re: New to AI Programming - 06-09-2006

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.


mirv the Silly Fish.
  
Reply With Quote
Re: New to AI Programming
Old
  (#4)
steved3298
Member
 
steved3298's Avatar
 
Status: Offline
Posts: 6
Join Date: Sep 2006
Default Re: New to AI Programming - 06-09-2006

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).
  
Reply With Quote
Re: New to AI Programming
Old
  (#5)
steved3298
Member
 
steved3298's Avatar
 
Status: Offline
Posts: 6
Join Date: Sep 2006
Default Re: New to AI Programming - 27-09-2006

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.
  
Reply With Quote
Re: New to AI Programming
Old
  (#6)
@$3.1415rin
Council Member, Author of JoeBOT
 
@$3.1415rin's Avatar
 
Status: Offline
Posts: 1,381
Join Date: Nov 2003
Location: Germany
Default Re: New to AI Programming - 27-09-2006

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


  
Reply With Quote
Re: New to AI Programming
Old
  (#7)
DrEvil
Member
 
DrEvil's Avatar
 
Status: Offline
Posts: 142
Join Date: Jan 2004
Location: Los Angeles, CA
Default Re: New to AI Programming - 28-09-2006

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.


Omni-bot AI framework
http://www.omni-bot.com

Foxbot - for Team Fortress Classic
http://www.foxbot.net



Last edited by DrEvil; 28-09-2006 at 01:07..
  
Reply With Quote
Re: New to AI Programming
Old
  (#8)
steved3298
Member
 
steved3298's Avatar
 
Status: Offline
Posts: 6
Join Date: Sep 2006
Default Re: New to AI Programming - 28-09-2006

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.
  
Reply With Quote
Re: New to AI Programming
Old
  (#9)
steved3298
Member
 
steved3298's Avatar
 
Status: Offline
Posts: 6
Join Date: Sep 2006
Default Re: New to AI Programming - 29-09-2006

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.
  
Reply With Quote
Re: New to AI Programming
Old
  (#10)
steved3298
Member
 
steved3298's Avatar
 
Status: Offline
Posts: 6
Join Date: Sep 2006
Default Re: New to AI Programming - 29-09-2006

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.
  
Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump



Powered by vBulletin® Version 3.8.2
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
vBulletin Skin developed by: vBStyles.com