Mapping a building for use in game (RADAR?)

[justing2k5]

Hi guys I hope I'm in the right subforum. I was thinking of a way to map a house or outside area with radar or some other method, and then using that info to create a map for a game.

So my question is, what are the different methods available for sensing the surrounding area and creating a map? It needs to be detailed enough where i can see the location of furniture, but nothing smaller than that. The map also needs to be in 3d.

Also, i'd like to convert and add this map into my game in realtime, so if i was moving around on my laptop with the sensing equipment it would update the map in the game as i moved. Is this possible?

Any help appreciated guys, I'm pretty lost here :(

 

[Danger]

Welcome to PF, Justing2k5.
You can use radar, sonar or a laser rangefinder (or even a pedometer) for the sensing aspect of it. What sort of interface and software you'd use to get it working with your computer, I have no idea.

 

[justing2k5]

Welcome to PF, Justing2k5.
You can use radar, sonar or a laser rangefinder (or even a pedometer) for the sensing aspect of it. What sort of interface and software you'd use to get it working with your computer, I have no idea.

Hi and thanks for the welcome! I was talking to a friend about this and he said the laser rangefinder the government uses to map the land before building a dam takes days!
Would you guys be able to verify this? I was hoping to map it in realtime as the game is actually being played so that wouldn't be ideal.

I don't know much about those other options you listed, would sonar be accurate enough and is radar easy to come by?

Thanks for the response :)

 

[berkeman]

Hi and thanks for the welcome! I was talking to a friend about this and he said the laser rangefinder the government uses to map the land before building a dam takes days!
Would you guys be able to verify this? I was hoping to map it in realtime as the game is actually being played so that wouldn't be ideal.

I don't know much about those other options you listed, would sonar be accurate enough and is radar easy to come by?

Sounds like a fun and challenging project. I encourage you to make it happen -- it will be unique, and you will learn a great deal from the various aspects of the project.

Your best bet IMO is to use a combination of sonar and laser mapping, plus some video --> 3-D reconstruction. I'd recommend that you read some of the papers written by a friend of mine at HP Labs, Tom Malzbender:

http://www.hpl.hp.com/personal/Tom_Malzbender/?jumpid=reg_R1002_USEN

Check out his paper on "Methods for Volumetric Reconstruction of Visual Scenes," for example. Amazing stuff.

Once you get a feel for some of the techniques that are used for volume reconstruction, you can think about how that applies to what you want to do. Home surveys are often done with sonar distance measuring devices (by real estate people and estimators, for example), and you should be able to find info on typical devices used by those folks. Just do a fairly refined google search, and that should turn up some info. Then think about how you could combine a video camera and the sonar thing on your laptop, along with you doing some input with a mouse, to define corners of the room, pieces of furniture, etc., as you move around. It would probably also help if you had the position information of the laptop as you move around, so maybe start off with a small tripod setup or something, with some measuring wheels that tell the laptop how you are moving the platform around in the room and between rooms...

At some point you might be able to simplify the tripod setup to just hand-carrying the laptop, and using a laser gyroscope or accelerometer or similar device to sense the motion of the platform...

Read through Tom's articles some, and do the search for the sonar device used by realtors, then come on back and tell us what you are thinking. Fun stuff -- make it happen!

 

[justing2k5]

WOW thanks berkeman that was immensely helpful! Definitely gave me lots of things to start with :D Especially that article you linked on volumetric reconstruction; it gave me a whole new way of looking at this (I had no idea you could do that!)

I'll be back once I read the article and perform some searches, Thanks again!

 

[Danger]

I couldn't even follow the abstract, but the pictures are nice.

 

[Mech_Engineer]

Also, i'd like to convert and add this map into my game in realtime, so if i was moving around on my laptop with the sensing equipment it would update the map in the game as i moved. Is this possible?

I was hoping to map it in realtime as the game is actually being played so that wouldn't be ideal.

I would say that if you are able to come up with a system that volumetrically maps and renders a room in real-time using just a laptop and some basic sensing equipment, your achievement will be far more important to robotics and navigation than a computer game. You want it to map the room as a 3-D mesh, and automatically texture that mesh using pictures of the room? That's going to take extremely advanced scanning equipment, serious algorithm computation, and some very serious comuting horsepower. I'm not really sure if what you're proposing is even possible with current sensing technologies.

Things like furniture may be hard to detect with certain sensors, not to mention miscompare conditions between different kinds of sensors. I suspect many of the issues you would run into are similar to problems seen on the DARPA Grand Challenge, as they use RADAR, LADAR, and photo comparing...

It should be a very interesting and cool thing to research, but I suspect the logistics of what you're proposing will be, shall we say, daunting. I do remember that a kid in some high school got expelled for making a CounterStrike map of his high school to play on with his friends, but he made it from scratch, not using a realtime sensing apparatus.

 

[russ_watters]

I'll see if I can find it, but there are devices out there that do exactly this. You set up the device in the middle of a room, stand back, and it fires a laser randomely into the room (thousands of pulses), mapping everything in it. I'm having trouble finding it, but here's a proposal for doing it outside: http://citeseer.ist.psu.edu/524036.html

There is also software that allows you to map a room using photographs. For that, though, you need to hang targets around the room so the software can align the frames and scale the distances. Here that is: http://www.photomodeler.com/index.htm

Also, look at this: http://www.cc.gatech.edu/ai/robot-lab/research/3d/

 

[vputz]

We used a device very similar contracted through Workhorse Technologies to map a cave, and I was able to use the derived data set with the http://www.cs.utexas.edu/~amenta/powercrust/welcome.html algorithm to whip up a shell that could be transformed and imported as a Quake map, although getting it to look interesting required a bit of work. So this sort of thing can be done, although in this case it was easy since the cave was empty and a radially-scanning robot could get pretty good information, and textures could be guessed (just make it look like rock!). Adding equipment, etc to the map took a lot of time by hand, as did lighting, and then rendering took QUITE a while to precalculate lightmaps (once that was done, running around the map was fast).

However, "in realtime" as mentioned may not be possible if you're trying to account for the MAP changing (moving furniture, etc). If you're just trying to account for things like player position, etc you can get away with GPS sensors on each player or some such.

 

[justing2k5]

Thanks for the replies everyone!

First let me clear up some details on my project - I wanted to take a PDA(or laptop) equipped with a digital video camera and have that feed displayed to its screen. Next I would superimpose monsters to it for me to blast! These monsters would be moving around based on my environment in real life (that is, no walking through walls or furniture). So, i won't be displaying the map i create for the game at all, it is only used for the monsters collision detection so it does not need to be that accurate. I think this is referred to as augmented reality.

So mech_engineer, i don't want to put the images of the room on the map, i just want to take a model of a monster and superimpose it on the video screen (which is getting feed from a video camera hooked up to it), and then have the monster be able to use the simple map created from scanners for the purpose of collision detection. I hope this clears things up a bit.

Ok so some of the problems i'll have to face are---

1.) My player location. How do i update my position in the game map as i move in real time? Needs to be quite accurate, within half a foot or so.

2.) Mapping the area. How do i create a rudimentary map of the area for my monsters to use?

For now let's ignore the problem of orienting the map based on the angle of the PDA.

For problem one I can think of 3 solutions.
1. Use GPS. I had heard GPS is only accurate to within 30 meters or so, so this wouldn't be good enough by itself for me to use. Perhaps some form of LPS? (Local Positioning system)

2. Use triangulation. I could use a form of triangulation if i had some WIFI routers or something set up around the area i'd be playing in.

3. Use an Inertial Navigation System. This system uses gyroscopes, accelerometers and other such contraptions to keep track of my movements.

For problem two

1. Premap the area before playing the game by measuring everything in the rooms by hand, or using the best tools I can find :P
2. Map the area in real time using image recognition, sonar, lasers, etc

The advantage of mapping in real time is is there would be no limit to where I could play as there is no work to be done beforehand (unless I'm using triangulation - would need to set up each transmitter).
But what I'm basically finding out from my research and from your guys' opinion, is that mapping in real time would be VERY difficult at this point in time. I will keep reading into how robots map their surroundings, however.

So let's say I decide to premap the area instead. Now my biggest problem is tracking my position within the game. What would be my best bet to tracking my position accurately within 6 inches, with the distance of let's say, a warehouse? Maybe something like this? http://www.acroname.com/robotics/parts/R275-NS-DEV-BUNDLE.html

Thank you all very much for your input!


PS - Thanks for the tip on powercrust vputz, i was looking for something like that. Now the only factor left to determine if this is possible is how fast sonar/laser scanners can generate those points! If its very fast, then it should be a big issue to get a rough idea of what the room looks like, just attach some sensors to my body and maybe spin around a few times? :D

russ_waters - I love the 3d maps shown on that last link you posted, I wonder how long it takes for the scanners to gather enough info to do that?? The citeseer link is down right now so i'll try it again later. Photomodeler seems like a great option for me if I were going to pre-map instead of realtime, i'll probably go with whichever method helps me pre-map the fastest in the end.

 

[Danger]

Now that I know what you're up to, I have a couple of suggestions about the playing hardware. If you can afford it, you should get a MacBook or MacBook Pro. They have a device called a 'Sudden Impact Detector' or 'Apple Impact Detector' which instantly locks the hard-drive head if the computer is jarred or dropped. It works on a multi-axis accelerometer setup along with tilt sensors. Some smart-asses have come up with a way to tap into the signals in order to use the laptop as a carpenter's level or seismograph. (I don't have those programmes, but I do have the iAlertU software which acts like a car alarm if someone tries to walk off with the machine.) It occurs to me that you might be able to capitalize upon that for position sensing within your game.
Some PowerBooks have the same system, but it's unknown as of now whether or not the aforementioned softwares will work with their OS.
You would need a lot of RAM to use this as your game platform, though, because the hard drive would lock up during manoeuvres.

edit: Another benefit is that these computers have an iSight camera built into the top of the display.