Difference between revisions of "User talk:Bnorm"

From Robowiki
Jump to navigation Jump to search
(→‎A*: Some little articles... ;))
(→‎A*: a bit on A* and Dijkstra)
Line 27: Line 27:
  
 
Regarding how to split the continuous space of robocode into discrete space, rather than splitting into squares I'd suggest you consider the approach of "navigation meshes" in [http://www.ai-blog.net/archives/000152.html this article] which I came across a while ago. With axis-aligned rectangles/squares as the only obstacles, as I believe is the case in VirtualCombat, it would be easy to set up. In addition, perhaps the techniques in [http://www.gamasutra.com/view/feature/3096/toward_more_realistic_pathfinding.php this article] may be relevant for how to route through the space? --[[User:Rednaxela|Rednaxela]] 01:23, 15 February 2011 (UTC)
 
Regarding how to split the continuous space of robocode into discrete space, rather than splitting into squares I'd suggest you consider the approach of "navigation meshes" in [http://www.ai-blog.net/archives/000152.html this article] which I came across a while ago. With axis-aligned rectangles/squares as the only obstacles, as I believe is the case in VirtualCombat, it would be easy to set up. In addition, perhaps the techniques in [http://www.gamasutra.com/view/feature/3096/toward_more_realistic_pathfinding.php this article] may be relevant for how to route through the space? --[[User:Rednaxela|Rednaxela]] 01:23, 15 February 2011 (UTC)
 +
 +
Doesn't the negative mesh pathfinding relay on collision mesh for actual movement? For example, wouldn't run into robots if you place a few, simple negative meshes? About A*, I think your original idea of searching is the best, but add a few angle between extremes too. And I don't think you have to do it on graph (i.e. you don't need to split battlefield), you could just take Manhattan distance (or Euclidian) of point to be the cost. If you have five angle and two accls. (accl and decel), you would yield ten branches. With just ten ticks or fifteen ticks you could do Dijkstra anyway (it is just A* without cost, just traditional BFS). --[[User:Nat|<span style="color:#099;">Nat</span>]] [[User talk:Nat|<span style="color:#0a5;">Pavasant</span>]] 12:30, 15 February 2011 (UTC)

Revision as of 13:30, 15 February 2011

Hey, nice to see you around again! --Voidious 05:24, 12 November 2007 (UTC)

  • Thanks! It's nice to know that somebody still remembers me, I never really was that active on the wiki... but it is nice to be back. This new wiki really got my attention, hope I can help out somehow. --KID 05:35, 12 November 2007 (UTC)

"I am a now 19 year old PSEO collage student who sends all his free time on his laptop programing robots." Same here, just in middle school and 13! =) At least you probably know trig. --Awesomeness 00:46, 4 May 2009 (UTC)

Google code

Anybody else around here use google code for a subversion server for their robocode source code? I just started getting into subversion and had a local server for awhile and just recently made the switch to google code. Just curious to know if I'm the only one... --KID 23:23, 4 January 2010 (UTC)

Personally I don't use Subversion or any SCM for Robocode robot, but I have seen people who have Google Code project for their miscellaneous code. One sad thing about Google Code is it isn't support RWPCL :P --Nat Pavasant 13:09, 5 January 2010 (UTC)

A*

So I'm currently taking an AI class and we've been talking a lot about search algorithms lately. As I am also currently involved in the VirtualCombat competition, I was curious to see if I could take one of these methods to help me find the best path from starting position to flag to home base. I know that the battlefield is constantly changing so I just couldn't find one path and stick with it, I'd have to be doing some recalculating every tick. I guess my question is if anybody knows of any robots that use this kind of method for movement or if any authors have done some research into this area. It would be great to know what you guys think.

It also just-so-happens that my next writing assignment for the class is on this very subject. :-P I'll find something to write either way, but I just thought other opinions wouldn't hurt.

--KID 20:33, 14 February 2011 (UTC)

This is a pretty important algorithm in path-finding: wikipedia:Dijkstra's algorithm. We covered it in an algorithms class I took in college. You could try to frame the problem in a form that algorithm could solve - at least that's probably where I'd start. I don't really know of any bots that do this, since the only obstacles in most Robocode battles are other bots, which pose other concerns than just pathing around them. :-) --Voidious 20:39, 14 February 2011 (UTC)

We have not actually talked about that algorithm yet. Maybe he's saving it for later. And you actually hit on the problem that I'm having the most trouble with: framing the problem. As Robocode is a continuous space, I have to come up with some way to put it into a discrete space for most of the algorithms we've talked about to work. My current idea is to use the limitations of a robots movement to help and only consider the extremes of heading change which should yield a branching factor of 9 at most I believe. (3 choices for heading, 2-3 choices for velocity) The other question is with a branching factor like that, how deep do I go? I think you would at least have to consider 20-30 ticks ahead. Which is way to many nodes. Thoughts? --KID 20:53, 14 February 2011 (UTC)

Ah, I actually didn't know what A* was, but after some Googling, it sounds superior to Dijkstra's. So I guess you can ignore that suggestion. Anyway, you could split the field up into squares and estimate a cost for moving through each one. Or just come up with a few random movement options and evaluate them, instead of all options. That starts to sound a lot like min risk, though. I might just try a min risk type movement with some factor to favor getting close to the base. Though that wouldn't satisfy a desire to implement an A* solution... And 20-30 ticks sounds like a lot, but might not be that bad with an efficient algorithm. Ok, I'm done rambling. =) --Voidious 21:12, 14 February 2011 (UTC)

I am currently using min risk for my team in VirtualCombat but what I have noticed is that they tend to have a hard time of moving around an object. They also like to get stuck on outside corners of objects too... Maybe I could combine the two in some way, find a point that I want to move to, then find the best path on how to get there. This path would only have to be calculated once as if something happens, I will have to pick a new point anyways. This could lead into some interesting thread use... hmm... I've always wanted to use those things in Robocode... Anyways, the problem that I have with splitting the field into a grid is that the bot won't be able to make it to some boxes and then how do you smooth the path you choice to make it efficient? The random movement option sounds interesting... I guess I'm just going to have to go do some Robocode programming in the name of homework... bummer... :-) --KID 21:24, 14 February 2011 (UTC)

Regarding how to split the continuous space of robocode into discrete space, rather than splitting into squares I'd suggest you consider the approach of "navigation meshes" in this article which I came across a while ago. With axis-aligned rectangles/squares as the only obstacles, as I believe is the case in VirtualCombat, it would be easy to set up. In addition, perhaps the techniques in this article may be relevant for how to route through the space? --Rednaxela 01:23, 15 February 2011 (UTC)

Doesn't the negative mesh pathfinding relay on collision mesh for actual movement? For example, wouldn't run into robots if you place a few, simple negative meshes? About A*, I think your original idea of searching is the best, but add a few angle between extremes too. And I don't think you have to do it on graph (i.e. you don't need to split battlefield), you could just take Manhattan distance (or Euclidian) of point to be the cost. If you have five angle and two accls. (accl and decel), you would yield ten branches. With just ten ticks or fifteen ticks you could do Dijkstra anyway (it is just A* without cost, just traditional BFS). --Nat Pavasant 12:30, 15 February 2011 (UTC)