User talk:Bnorm - Revision history

Voidious: Voidious moved page User talk:KID to User talk:Bnorm: Automatically moved page while renaming the user "KID" to "Bnorm"

2013-05-08T04:22:25Z

Voidious moved page User talk:KID to User talk:Bnorm: Automatically moved page while renaming the user "KID" to "Bnorm"

Bnorm: /* A* */ Waypoints?

2011-02-16T22:55:46Z

A*: Waypoints?

Nat: /* A* / a bit on A and Dijkstra

2011-02-15T12:30:22Z

A*: a bit on A* and Dijkstra

Rednaxela: /* A* */ Some little articles... ;)

2011-02-15T01:23:41Z

A*: Some little articles... ;)

Bnorm: /* A* */

2011-02-14T21:24:27Z

Voidious: /* A* */ comment

2011-02-14T21:12:42Z

A*: comment

Bnorm: /* A* */ Framing the problem

2011-02-14T20:53:19Z

A*: Framing the problem

Voidious: /* A* */ sig

2011-02-14T20:39:35Z

A*: sig

Voidious: /* A* */ Dijkstra's?

2011-02-14T20:39:22Z

A*: Dijkstra's?

Bnorm: /* A* */ new section

2011-02-14T20:33:59Z

A*: new section

← Older revision		Revision as of 22:55, 16 February 2011
Line 29:		Line 29:

	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)		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)
		+
		+	Another idea that I had to stir the pot: what about waypoints? If we statically create a bunch of waypoints throughout the map at the beginning of a match and remove paths and nodes as objects are discovered this might provide a waypoint system that would be a lot simpler to find a path through. Then the bot could just be told which waypoint it's trying to get to next. This of course would only have to be used as long as the path between the bot and it's destination is blocked by some object, otherwise just go straight for it. --[[User:KID\|KID]] 22:55, 16 February 2011 (UTC)

← Older revision		Revision as of 12:30, 15 February 2011
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)

← Older revision		Revision as of 01:23, 15 February 2011
Line 25:		Line 25:

	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... :-) --[[User:KID\|KID]] 21:24, 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... :-) --[[User:KID\|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 [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)

← Older revision		Revision as of 21:24, 14 February 2011
Line 23:		Line 23:

	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. =) --[[User:Voidious\|Voidious]] 21:12, 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. =) --[[User:Voidious\|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... :-) --[[User:KID\|KID]] 21:24, 14 February 2011 (UTC)

← Older revision		Revision as of 21:12, 14 February 2011
Line 21:		Line 21:

	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? --[[User:KID\|KID]] 20:53, 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? --[[User:KID\|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. =) --[[User:Voidious\|Voidious]] 21:12, 14 February 2011 (UTC)

← Older revision		Revision as of 20:53, 14 February 2011
Line 19:		Line 19:

	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. :-) --[[User:Voidious\|Voidious]] 20:39, 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. :-) --[[User:Voidious\|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? --[[User:KID\|KID]] 20:53, 14 February 2011 (UTC)

← Older revision		Revision as of 20:39, 14 February 2011
Line 18:		Line 18:
	--[[User:KID\|KID]] 20:33, 14 February 2011 (UTC)		--[[User:KID\|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. :-)	+	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. :-) --[[User:Voidious\|Voidious]] 20:39, 14 February 2011 (UTC)

← Older revision		Revision as of 20:39, 14 February 2011
Line 17:		Line 17:

	--[[User:KID\|KID]] 20:33, 14 February 2011 (UTC)		--[[User:KID\|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. :-)

← Older revision		Revision as of 20:33, 14 February 2011
Line 9:		Line 9:

	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 --[[User:Nat\|<span style="color:#099;">Nat</span>]] [[User talk:Nat\|<span style="color:#0a5;">Pavasant</span>]] 13:09, 5 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 --[[User:Nat\|<span style="color:#099;">Nat</span>]] [[User talk:Nat\|<span style="color:#0a5;">Pavasant</span>]] 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.
		+
		+	--[[User:KID\|KID]] 20:33, 14 February 2011 (UTC)