Archived

This topic is now archived and is closed to further replies.

dalleboy

Why mapping?

Recommended Posts

Why should we have to map the surroundings of the bot instead of concentrating on the AI for the bot? Everyone (that stands a chance of winning the contest) will have to do some type of mapping, the solution of this will be somewhat different but the results will be the same. The mapping is only one extra layer of the problem, and I think it is totally unnecessary. The GDArena API does not provide sufficient functions for checking if a move/turn/strafe/anything-else fails or not, and what the result of the move/turn/strafe/anything-else really is. You can only guess that the SetSpeed(SET_HIGH_SPEED) moves the bot 0.8888 units forward, but as SetSpeed will return true even if the move resulted in moving the bot 0.2672 units forward or 0.5367 units forward because of a collision with something else. My proposal is: - Add the function GetMyXPosition that returns the x position for the bot on the map relative to the left of the map. - Add the function GetMyYPosition that returns the y position for the bot on the map relative to the top of the map. - Add the function GetMyRotation that returns the rotation for the bot on the map relative to the top of the map. - Add the function GetNumStaticObjects that returns the number of static (rocks & trees) objects on the map. - Add the function GetStaticObject that returns information (type, position, radius) about a specific static object on the map. - Add the function GetXSize that returns the x size of the map. - Add the function GetYSize that returns the y size of the map. - Change the GetNumObjectsInSight and GetObjectsInSight functions to only handle non-static (enemy, grenades & ammo) objects. OR: - Change the movement functions so that they (in some way) report their (level-of) success and the result accordingly. [How To Ask Questions|STL Programmer''s Guide|Bjarne FAQ|C++ FAQ Lite|C++ Reference|MSDN]

Share this post


Link to post
Share on other sites
I think the whole point of it is to let the Bot/Program learn the map by itself.

Think of it this way.
You get given a paintball gun and an exploding lemon (well its yellow like in gdarena).
Then you get blind folded and whacked in a forest.
Blind fold gets removed and you have to get your orientation back, and not get lost whilst you try and scon the other bloke with the lemon.

Share this post


Link to post
Share on other sites
quote:
Original post by Dredge-Master I think the whole point of it is to let the Bot/Program learn the map by itself.

I have nothing against the actual learning process, it is that the GDArena API is written in such way that it impairs the learning process.

A so-so working mapping is not hard to code using the GDArena API, I''ve already written one.

quote:
Original post by Dredge-Master Think of it this way.
You get given a paintball gun and an exploding lemon (well its yellow like in gdarena).
Then you get blind folded and whacked in a forest.
Blind fold gets removed and you have to get your orientation back, and not get lost whilst you try and scon the other bloke with the lemon.

If you run around in the woods with a paintball gun and an exploding lemon you would tell if you run into a tree, would you not?

I think GDArena would get a lot more entries if it where a bit easier to use.

[How To Ask Questions|STL Programmer''s Guide|Bjarne FAQ|C++ FAQ Lite|C++ Reference|MSDN]

Share this post


Link to post
Share on other sites
Well it does give you the distance to the tree and we know how big the trees are in gdarena.

Rocks are a bit annoying though as we can''t tell which are small or big though.

Share this post


Link to post
Share on other sites
quote:
Original post by dalleboy
quote:
Original post by Dredge-Master I think the whole point of it is to let the Bot/Program learn the map by itself.

I have nothing against the actual learning process, it is that the GDArena API is written in such way that it impairs the learning process.

A so-so working mapping is not hard to code using the GDArena API, I''ve already written one.

quote:
Original post by Dredge-Master Think of it this way.
You get given a paintball gun and an exploding lemon (well its yellow like in gdarena).
Then you get blind folded and whacked in a forest.
Blind fold gets removed and you have to get your orientation back, and not get lost whilst you try and scon the other bloke with the lemon.

If you run around in the woods with a paintball gun and an exploding lemon you would tell if you run into a tree, would you not?

I think GDArena would get a lot more entries if it where a bit easier to use.

[How To Ask Questions|STL Programmer''s Guide|Bjarne FAQ|C++ FAQ Lite|C++ Reference|MSDN]


I think the point he was making is that we don''t have a GPS system built into our heads, we have to use are sences to navigate our world reletive to everything else.

I can agree partly with the splitting up of static and non-static objects up in the get sight type functions, but it is not crucial since the objects can be split up in a function/class that manages your FOV (assuming you use one). Personally i like just having one list of all objects in your view, and then just sorting the list myself in a way i want to use it.

Anything todo with exact orientation though would make it to easy, and more harder for those like me with little experiance in AI (if it was pure coord based).

Just my opinion,

-J

Share this post


Link to post
Share on other sites
I can see exactly why we''re got given absolute positions, but I do think we should be able to tell if the direction we attempt to move in is blocked. For instance if you''re strafing you just can''t see anything!

Share this post


Link to post
Share on other sites
Aside from never letting your bot walk into trees or rocks, it''s relatively easy to determine how far you moved in what direction each cycle, as long as you have something in view, by comparing their previous distances/directions with their new ones.

For the part about static and non-static objects, it''s easy enough to sort them out on your own, or if you wanted, it would take very little time to write functions that did it for you.

For the part about GetXSize & GetYSize - the map is 320x240.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
i tell you what. if the interface to the arena is changed so that you can get fixed positions, directions, etc. out of it, then to me this contest becomes a dud and misses out on a large part of what is there to be learned.

you don''t need a map to navigate and you don''t need a map to keep the bot from getting stuck and you don''t need a map to do good.

a good part of a real bot''s AI is navigation and even today very few bots navigate via GPS. navigation is as much about AI as is any other aspect of this contest.

Share this post


Link to post
Share on other sites
I don''t think there is any need to be given information about your position, or even information about movement. When you''re playing an FPS (for example) you don''t get tactile feedback about whether you''ve hit something. All you get is audio-visual input, and yet it''s perfectly easy for you to tell when you''re moving, and when you''re not, and how far you''ve moved. You can even turn the sound off, and you can still tell very easily whether you''re moving, and how much, so therefore, the only required inputs to be able to measure your movement are visual, and your brain is simply converting this into positional information. So obviously, the inputs to the bot are enough to let it calculate its movement quite easily. Or at least, they would be if there was always something in view[1].

You may think that it''s very hard to make a system like that, but it really isn''t. I''ve already got a bot that can tell whether it''s actually moving, based on visible objects, and it works very well, and was easy to implement.

Other than that, the arena is pretty small at the moment, and there aren''t that many options for what you can do in any one update, so giving the bot positional information on a plate would just take away an interesting challenge (even if it isn''t an extremely challenging challenge)

John B

[1] The problem of not always having static objects in your field of view, that you can use for reference is something that should be addressed in my opinion.

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
you don''t need a map to navigate and you don''t need a map to keep the bot from getting stuck and you don''t need a map to do good.

That''s true - you can get a long way without a map. But I think having a map does allow some slightly more intelligent decisions to be made. For example, if you''re backing away from the enemy, and you want to strafe, a map can be used to decide whether to strafe to the left, or to the right. If there''s a tree on the left that you don''t want to get stuck on, and there''s a tree futher forward on the right that you can try and hide behind, it''s obvious you should strafe to the right - but without a map, it would be impossible to tell which way would be better, and you could easily get stuck on an object that isn''t in your field of view, giving the enemy bot a target that isn''t moving.

John B

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
granted, for the best bot an internal map would probably be required. but under no circumstances does this information need to be provided by the arena. it is all easily enough calculated. and that is part of AI.

but i disagree with your point [1] above. the lack of any visual information is information in and of itself. it''s what my bot''s use to avoid getting trapped in corners and against the walls.

Share this post


Link to post
Share on other sites
The point isn''t that the mapping is really hard to write, I''ve already written it, but I think it is an unnecessary extra layer that really doesn''t add much to the problem. That extra layer could prevent some people from getting started on GDArena because they could think the API is hard to get started with.

[How To Ask Questions|STL Programmer''s Guide|Bjarne FAQ|C++ FAQ Lite|C++ Reference|MSDN]

Share this post


Link to post
Share on other sites
The whole point of this contest is that new techniques are brought into use, than the ones used in conventional AI. If you''re having problems overcoming the problem of hitting into things, then it''s your problem, not the lack of information.

I think that a nicer way to give input to the bot wouldn''t be as a series of coordinates, but as what the bot actually sees, so a line of colour. Obviously it''s a 2D ''game'', so a 2D view is not required. Then only estimations on the distance to an object could be calculated.

The whole AI would have to take into account the fact that the map isn''t exact. The skill in the contest would be to make a good map, rather than experience in coding AI. In my opinion that would be far more fun. But I''m sure most others would disagree.

Share this post


Link to post
Share on other sites
I like the system the way it is. I''ve only spent a few hours coming up with a mapping system, and it''s nearly complete. Different people will do it different ways and be more clever or less. I like that.

The FPS analogy doesn''t work for one reason: a player can easily follow objects as they move relative to you. The appropriate analogy to GDArena would be to assign object IDs that could be tracked. But I don''t think I''d want that. Clever engineering is as much a part of AI as pure AI theory.

I like pie.

Share this post


Link to post
Share on other sites
quote:
Original post by RenderTarget
The FPS analogy doesn''t work for one reason: a player can easily follow objects as they move relative to you. The appropriate analogy to GDArena would be to assign object IDs that could be tracked. But I don''t think I''d want that. Clever engineering is as much a part of AI as pure AI theory.

I think the FPS analogy does work. Certainly a player can follow objects as they move through the world, but they do it frame by frame, just as a GDArena bot can do it frame by frame. Object IDs can be used to track object movement, but that doesn''t mean the object IDs have to be given to the bot by the arena. Given that the maximum distance you can move in a single update isn''t very far (it''s less than the minimum distance between two objects afaik), it''s perfectly possible for the bot to recognise and track objects based on position and type, just as an FPS player recognises and tracks objects based on their position, shape and texture.

John B

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
granted, for the best bot an internal map would probably be required. but under no circumstances does this information need to be provided by the arena. it is all easily enough calculated. and that is part of AI.

but i disagree with your point [1] above. the lack of any visual information is information in and of itself. it''s what my bot''s use to avoid getting trapped in corners and against the walls.


I had a map calculating thing, but the screwy wall collision (and wall in view) routines screw the map up completely, so I dropped it. I had it building a map based on the objects I saw oriented to the original start position, and it worked great until I either hit something not in view, or slid along a wall. I don''t think it should all be given to you, but there should be some way of figuring out how far you moved, in real life (paintball example), you KNOW when you stopped, or walked into a tree, etc, so you know you stopped moving. In a FPS, you know when you are sliding because you can see it and react to it, but the bot has no such indications, so you can''t react to it.

Share this post


Link to post
Share on other sites
quote:
Original post by JohnBSmall
quote:
Original post by RenderTarget
The FPS analogy doesn''t work for one reason: a player can easily follow objects as they move relative to you. The appropriate analogy to GDArena would be to assign object IDs that could be tracked. But I don''t think I''d want that. Clever engineering is as much a part of AI as pure AI theory.

I think the FPS analogy does work. Certainly a player can follow objects as they move through the world, but they do it frame by frame, just as a GDArena bot can do it frame by frame. Object IDs can be used to track object movement, but that doesn''t mean the object IDs have to be given to the bot by the arena. Given that the maximum distance you can move in a single update isn''t very far (it''s less than the minimum distance between two objects afaik), it''s perfectly possible for the bot to recognise and track objects based on position and type, just as an FPS player recognises and tracks objects based on their position, shape and texture.

John B



Yes, but the player builds a visual map of the arena in his mind after seeing it, therefore building a map. It''s almost impossible to build a useable map in GD Arena due to the way wall viewing and collisions happen, and not knowing when you''re strafing into something, etc. In a FPS, you know when you''re sliding along a wall, or stop because you hit something.. the bot gets no indication that he stopped, or is sliding along something, so if these problems where fixed (give us a movement delta between frames or something!), we could build a map and avoid collisions (and tell when we''re stuck) much more easily.

Share this post


Link to post
Share on other sites
quote:


Yes, but the player builds a visual map of the arena in his mind after seeing it, therefore building a map. It''s almost impossible to build a useable map in GD Arena due to the way wall viewing and collisions happen, and not knowing when you''re strafing into something, etc. In a FPS, you know when you''re sliding along a wall, or stop because you hit something.. the bot gets no indication that he stopped, or is sliding along something, so if these problems where fixed (give us a movement delta between frames or something!), we could build a map and avoid collisions (and tell when we''re stuck) much more easily.



yes, for the most part i agree.
another example: say you are playing an fps.
even if you cannot see *any* distinct game object to track your movement by(for example you are standing on a perfectly flat plane which extends as far as you can see in all directions) , you can still tell that you are moving, and the direction you are moving, as long as the plane is TEXTURED. by watching the "movement" of the pattern of the texture, you can deduce which way you are moving. therefore, i agree that it would be useful to have either the bot''s movement delta (not even the direction of movement, just a float representing the distance of travel!) or whether it has collided with something.
i don''t think this will really be much of an issue, however, because kevin has said that he wants to add a small circle around the bot to the bot''s FOV (so the FOV would be a little circle, with a cone radiating out from it). this would make things MUCH more workable, as you would always see if you were about to collide with an object (including WALLS!).

A headache, ancillary; an hourglass auxiliary.

"something witty, blah, blah, blah"
--That One Witty Guy (remember? that one dude?)


Share this post


Link to post
Share on other sites
quote:
Original post by Ready4Dis
Yes, but the player builds a visual map of the arena in his mind after seeing it, therefore building a map. It''s almost impossible to build a useable map in GD Arena due to the way wall viewing and collisions happen, and not knowing when you''re strafing into something, etc. In a FPS, you know when you''re sliding along a wall, or stop because you hit something.. the bot gets no indication that he stopped, or is sliding along something, so if these problems where fixed (give us a movement delta between frames or something!), we could build a map and avoid collisions (and tell when we''re stuck) much more easily.

In an FPS, you only know you''ve stopped, because the objects you see on screen aren''t moving any more, even though you''re pressing the button. It''s the same in GDArena. As I''ve said before, it''s perfectly possible to tell when you''re not moving based on objects that you can see. Partial movement (sliding along a wall) is harder, but not impossible to deal with. And although there are positions where there is absolutely nothing the bot can ''see'', they happen in and around the corners of the map, and can simply be used as an indication that you''re facing away from the bulk of the map, and should therefore turn round.

John B

Share this post


Link to post
Share on other sites
quote:
another example: say you are playing an fps.
even if you cannot see *any* distinct game object to track your movement by(for example you are standing on a perfectly flat plane which extends as far as you can see in all directions) , you can still tell that you are moving, and the direction you are moving, as long as the plane is TEXTURED.

In this example, the object you can see is the floor. The analogy in GDArena would be if the only object the bot can see is a wall, but even this small bit of information (just a direction to the wall, and a distance) is enough to track movement.

Edit:
quote:
i don't think this will really be much of an issue, however, because kevin has said that he wants to add a small circle around the bot to the bot's FOV (so the FOV would be a little circle, with a cone radiating out from it). this would make things MUCH more workable, as you would always see if you were about to collide with an object (including WALLS!).

I'd agree with this, although actually I think the change should simply be that you can always see any walls in your FOV, instead of only when a perpendicular line to the wall is in your FOV.

John B

[edited by - JohnBSmall on August 13, 2003 7:38:50 PM]

Share this post


Link to post
Share on other sites
Yes, it''s pretty annoying having my FOV lines in a wall, yet my bot can''t see it. If he fixes that issue, I''m pretty much set, as that was the only thing (sliding on a wall) hindering me from building the map properly .

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by Ready4Dis
I had a map calculating thing, but the screwy wall collision (and wall in view) routines screw the map up completely, so I dropped it. I had it building a map based on the objects I saw oriented to the original start position, and it worked great until I either hit something not in view, or slid along a wall. I don''t think it should all be given to you, but there should be some way of figuring out how far you moved, in real life (paintball example), you KNOW when you stopped, or walked into a tree, etc, so you know you stopped moving. In a FPS, you know when you are sliding because you can see it and react to it, but the bot has no such indications, so you can''t react to it.

i don''t know. maybe i''ve approached things differently but i like things the way they are. and i hope the effort i''ve put into the navigation module of my bots doesn''t go to waste.

Share this post


Link to post
Share on other sites
if you run headlong into a tree (most of us aren''t that dumb) you might flail around for a bit, but the way a human figures it out is by his surroundings to see exactly where he is.

The bot can do the same thing.

I''ve programmed mine with a standard human-like orientation (or disorrientation) so it''s fine now for the entire map. Knows where everything is, and if it gets lost (walks headlong into a wall and can''t see anything) it can find itself again quite happily.

I also hope that it doesn''t get changed, although I do admit that if we could find out something like if we didn''t move the full length it would make it overly easy, but would save me about 30 lines of code and around 528bytes of extra data.

If it isn''t atleast semi difficult, whats the point of having a contest?

Share this post


Link to post
Share on other sites
quote:
Original post by Dredge-Master
if you run headlong into a tree (most of us aren''t that dumb) you might flail around for a bit, but the way a human figures it out is by his surroundings to see exactly where he is.

The bot can do the same thing.

I''ve programmed mine with a standard human-like orientation (or disorrientation) so it''s fine now for the entire map. Knows where everything is, and if it gets lost (walks headlong into a wall and can''t see anything) it can find itself again quite happily.

I also hope that it doesn''t get changed, although I do admit that if we could find out something like if we didn''t move the full length it would make it overly easy, but would save me about 30 lines of code and around 528bytes of extra data.

If it isn''t atleast semi difficult, whats the point of having a contest?


Yes, but how do you handle things like when you walk into an object that you didn''t ever see... or slide across a wall? How I was building my map, it was based on knowing how I was moving, which ultimately failed once I didn''t know how far I had moved (sliding, getting stuck on something out of view, etc). Obviously, I can check if the distance moved against another object in view is correct or not, but if it''s not, I still don''t know which direction I''m off by. Maybe I slid left a bit, but the distance on tells me how far I should be now, doesn''t say which direction I could have moved. I''d be interested to hear how you are mapping the entire world and handling these cases, but if you don''t want to give out your secret, that''s cool too .

Share this post


Link to post
Share on other sites
quote:
Original post by Ready4Dis
Obviously, I can check if the distance moved against another object in view is correct or not, but if it's not, I still don't know which direction I'm off by. Maybe I slid left a bit, but the distance on tells me how far I should be now, doesn't say which direction I could have moved. I'd be interested to hear how you are mapping the entire world and handling these cases, but if you don't want to give out your secret, that's cool too .

That's how my first version worked, and of course the map broke when the bot slid on a wall. But I've just added some code to calculate how far it's actually moved. As long as it can match some objects in view with objects in its map (which is very easy - at least if you're using the simple, brute force approach as I am) you can calculate where you've actually moved, and use that to compensate if you back into a wall and slide.
Right now, I'm thinking about what other information I can use from the walls. My code already matches walls to check for movement as a boolean (so if you back into a tree, and the only thing in view is a wall, it can compensate) but I think it may be possible even to compensate for sliding against a wall - even if the only thing you can see is the wall you're sliding against.

Edit: I'm not actually going to give you my code, for 3 reasons: 1) It's very, very easy to add, if you've already got boolean movement checking. 2) This is a contest. 3) I want to see how other people handle it, and the more people that write code completely on their own, the more ways it will be handled.

John B

[edited by - JohnBSmall on August 13, 2003 9:44:17 PM]

Share this post


Link to post
Share on other sites