[edited by - Peon on August 24, 2003 6:00:13 PM]
🎉 Celebrating 25 Years of GameDev.net! 🎉
Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!
How would you do mapping?
Author
I've been working on pretty much what I think most people have -- random searching -- and I think I need to improve on my bot a bit. I think I will finish up my obstacle avoidance code just to learn a bit more about it, but I want to try mapping too. I might just have two modes for moving about the map: a random search until I reach a certain percentage of the map viewed, and then switch to 'mapped' mode; I'm not sure yet. Here's what I'm currently thinking, so help me out here:
1. I declare an array of type int that is the same size as the playing field (actually, maybe even twice as large; I'll explain why later)
2. I would record my initial coordinates as 0,0. The point I am on the map doesn't matter at all; my robot simply knows that to him, he is at (0,0). The reason I would need to declare an array of a larger size than I need is because I really donm't know where I am, and so I could theoretically move out of the array bounds if the map is the "correct" size.
3. I start moving about the map. My own position is calculated using (cos(of the angle I travel at) * distance traveled = delta-x). Same for my y-position, but I would use sine. Distance traveled is calculated through a custom Move() function I wrote that, depending on your speed, will add the correct number of UPS (units per update) to your distance traveled. If distance traveled becomes too large without any turns to avoid something, I'm probably stuck, and my position would be reset to the correct amount (since I wasn't REALLY moving anywhere) Furhtermore, the mapping should help avoid objects, anyway. This would be calculated every update.
4. As I go along, I also keep track of all the objects I see and put them in the array. I am assuming that when you see the distance to an object, it means the center of the object. Once an object was spotted, I would ID it, and fill in a "circle of 1's" around the center of the object in my array (to show that terrain is present there)
5. If I spot an enemy, I put him as a '2' in the array. I track his movement for several updates and try and see if he is following a straight path; if so, I can attempt to grenade him, or move to cut him off at a location in front of him (hopefully mapped out, already) If I really want to get fancy, I would use some sort of 'threat assesment' that someone else suggested; each square would then be assigned a value, depending on the likelihood of the enemy being there.
6. If I lose track of the enemy, I head to his last known location and bearing, and see if I can pick up the trail again.
As opposed to random searching, I also thought about using waypoints to guide him around the map. Using my initial positon as 0,0, I could tell him to travel to WP1 @ (-20,0), WP2 @ (20,0), etc... I'm not sure if that would be more efficient that random searching, but I'd imagine it would.
Pathfinding would use something like A* I think, but I have no experience with it whatsoever
Any thoughts? Is there a better way to do this? If I can fix up my random search / obstacle avoidance and get some mapping in there, I'd be glad to release the source code for anyone who's interested.
EDIT: Wow, this is really long, I apologize; anyone who reads and comments get a free caek though
[edited by - Peon on August 24, 2003 6:00:13 PM]
[edited by - Peon on August 24, 2003 6:00:13 PM]
As it stands, you shouldn''t need to have a map which is twice as big as the actual arena, because you have walls. Originally the map array had to theoretically be twice as large as the diagonal of the arena because since you had to assume your start was 0,0, the worst-case-scenario would have been you start in a corner and one of your axis was aligned with the diagonal. However, now that we have walls, you only really need an array of 320x320. What my bot does at the start is turns until it''s spotted two of the walls, then aligns its position and angle relative to those walls - it makes the assumption that one of the walls is the east wall and the other one the north, but it doesn''t really matter if it''s true or not, as long as one is a north/south wall and one is an east/west.
But aside from that, a few things to consider - if you ever walk into an object, your map will get ''corrupted'' with false data, because your pos variable will change even though you aren''t moving, so because everything is relative to your bot''s position, your bot will think it''s seeing new objects when really it''s just seeing the same objects and not moving. You can reset your bots position, but that doesn''t help get rid of all the ghost objects on your map. You''ll either have to make sure your pathfinding never allows you to walk into objects ever, or you can alternatively always keep track of one of the objects in your view frustrum and every cycle check your movement relative to its position and make sure everything adds up.
But aside from that, a few things to consider - if you ever walk into an object, your map will get ''corrupted'' with false data, because your pos variable will change even though you aren''t moving, so because everything is relative to your bot''s position, your bot will think it''s seeing new objects when really it''s just seeing the same objects and not moving. You can reset your bots position, but that doesn''t help get rid of all the ghost objects on your map. You''ll either have to make sure your pathfinding never allows you to walk into objects ever, or you can alternatively always keep track of one of the objects in your view frustrum and every cycle check your movement relative to its position and make sure everything adds up.
Simpy create an Object data structure, and just store a list of objects that have been seen. If you find an object that is within another objects radius, you know that it''s the same object, and the players location must be off by a tiny bit, so you take the objects location and subtract it from the current calculated position, then you add that to your player location to correct it . This works great as long as you keep at least one object in view while moving (so if you see nothing, or nothing but walls, turn until you spot an object). I''m still trying to work out the kinks in my mapping, but why store a huge array when you can just store a list of objects + radius + type info.
. This works great as long as you keep at least one object in view while moving (so if you see nothing, or nothing but walls, turn until you spot an object). I''m still trying to work out the kinks in my mapping, but why store a huge array when you can just store a list of objects + radius + type info.
just so you know: my mapping uses a combination of a list of objects + a 200*200 units wide map scaled to a dimension of 800*800arenaunits. you will notice that i dont get a hard performance impact when my bot is active so ive done some tricks to use only the important part of the map, its actually eating [lemme calc: 200*200*(2float+1int)= wow] 480kb and is used for my pathfinding algo and some other stuff... i wanted to use a polygonal approach but my polygon class sux a bit 
...
1./2. yes but if you want to cover the whole area you have to calc the max dist in the arena, thats sqrt(320²+240²)=400units in each direction => 800x800 array. thats a big array and it will eat all your cpu time if you waste cpu time like i did
you could alternatively build your map with linked arrays of smaller sizes...
3.if you only walk into areas you have previously seen and they are obstaclefree you cant get stuck... u have to add some additional area around obstacles (my is 1.6 currently) and walls(5) where you bot shouldn move otherwhise you can get stuck
4. 1ses, i love 1ses so i use them for the accesible ground (where bot can move)
5. not a good idea i think, the bots move to fast and the arena is to small, a bot can travel in 10sec over the woule map... but maybe worth to try it...the map-resolution cant hold the exact position...
6. yep helps (my bot does this, my bot is also STopID sometimes showing inteligent behaviour...)
pls dont share to much source, its a sort of contest and not a copy my source and rename it to get a god bot...
@HappyDude: yeah and your bot also needs an extra rotation@startup
T2k
...1./2. yes but if you want to cover the whole area you have to calc the max dist in the arena, thats sqrt(320²+240²)=400units in each direction => 800x800 array. thats a big array and it will eat all your cpu time if you waste cpu time like i did
you could alternatively build your map with linked arrays of smaller sizes...
3.if you only walk into areas you have previously seen and they are obstaclefree you cant get stuck... u have to add some additional area around obstacles (my is 1.6 currently) and walls(5) where you bot shouldn move otherwhise you can get stuck
4. 1ses, i love 1ses so i use them for the accesible ground (where bot can move)
5. not a good idea i think, the bots move to fast and the arena is to small, a bot can travel in 10sec over the woule map... but maybe worth to try it...the map-resolution cant hold the exact position...
6. yep helps (my bot does this, my bot is also STopID
sometimes showing inteligent behaviour...)pls dont share to much source, its a sort of contest and not a copy my source and rename it to get a god bot...
@HappyDude: yeah and your bot also needs an extra rotation@startup
T2k
Author
quote:I wouldn''t worry too much. I''ve never programmed AI before, so I doubt that anything I released would be THAT valuable. More to help other newbies get started
pls dont share to much source, its a sort of contest and not a copy my source and rename it to get a god bot...
Ready4Dis: I guess I thought of an array because it was something I could visualize better, but you''re right; a list of objects would probably be a lot more efficient.
How are you guys doing the pathfinding itself? Some version of an AStar implementation or what? I read an AStar tutorial and is definetly over my head at this point, so I am looking for some other ideas that I might be able to use. A map, no matter how good, won''t help unless you can calculate a path through it.
i think iam using a "breath first" method, nothing complex but ive added the abbility that if the point couldnt be reached then it takes the closest point to the target
T2k
T2k
I'm still working on both the coordinating system and the mapping system.
Right now I've got a keyboard-controlled bot (this just makes debugging a lot easier). I don't have a working mapping system yet, but the bot refuses to walk "through" objects just by checking the distance parameter. Simple, but effective
[edited by - Epidemi on August 26, 2003 5:46:13 PM]
Right now I've got a keyboard-controlled bot (this just makes debugging a lot easier). I don't have a working mapping system yet, but the bot refuses to walk "through" objects just by checking the distance parameter. Simple, but effective
[edited by - Epidemi on August 26, 2003 5:46:13 PM]
You don't need to use any big spatial arrays. Just keep an array or list of objects you have seen so far. Something like this maybe:
And then figure out how to detect when you see something you already know about.
[edited by - Martel on August 27, 2003 3:08:52 AM]
struct Entity { ObjectType type; float x, y; float radius; float facing;};std::vector< Entity* > entities;And then figure out how to detect when you see something you already know about.
[edited by - Martel on August 27, 2003 3:08:52 AM]
quote: Original post by Peonquote:I wouldn't worry too much. I've never programmed AI before, so I doubt that anything I released would be THAT valuable. More to help other newbies get started
pls dont share to much source, its a sort of contest and not a copy my source and rename it to get a god bot...
Ready4Dis: I guess I thought of an array because it was something I could visualize better, but you're right; a list of objects would probably be a lot more efficient.
How are you guys doing the pathfinding itself? Some version of an AStar implementation or what? I read an AStar tutorial and is definetly over my head at this point, so I am looking for some other ideas that I might be able to use. A map, no matter how good, won't help unless you can calculate a path through it.
If you haven't already, look here:
http://www-cs-students.stanford.edu/~amitp/gameprog.html#Paths
Dijkstra's shortest path algorithm is the basis for A* and may be a bit easier to understand.
[edited by - Martel on August 27, 2003 3:07:08 AM]
Author
quote:Wow, they have a great A* tutorial there for beginners. I thought the one I was looking at before, but this takes the cake; the pictures definetly helped a lot.
If you haven''t already, look here:
http://www-cs-students.stanford.edu/~amitp/gameprog.html#Paths
Dijkstra''s shortest path algorithm is the basis for A* and may be a bit easier to understand.
I''ll probably end up trying to implement this in a console before I try and do it on my bot. I still haven''t gotten the random-bump-into-object-then-turn code to work, so I''m counting on mapping to help me out; we''ll see.
Thanks
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
