Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

So I am undertaking a project which does navigation sort of thing. So here is how the problem statement looks like.

Say, given a map of a floor, with different rooms, now somehow, this information is provided to the program and what the program does is, it takes two more inputs,

The starting location. The final location. Now having had these two locations, the program draws out the best possible route from starting to ending location. I will be using C language for the implementation of code.

Now, the problems:

  1. How do I provide the information about the floor, i.e. whether there's a wall or a door or just empty space, to my program. Here's my take on it. I will have a 2-D matrix, where in the 1 in the matrix shows an empty space, and a 0 signifies a wall. But now I am not sure, how to mark a cell as 0. i.e how the dimensions of the matrix shall be chosen? For example, say my floor is 8 by 8 (length units). Now shall my matrix be 8 by 8 or 16 by 16 or what? And what if, having chosen the dimension of a single cell, if some part of the cell is wall and the other is empty space, shall it be a 0 or a 1? But I guess, it would be a manual input after all? But I dont expect someone to create this kind of matrix for me manually? So, some help in this direction will be appreciated? Is this way of representing the data allright, or shall I go about in a different direction?
  2. Say, If I go by the above way of data representation, what do I do next? I was thinking, somehow, I will have to convert that matrix of data into a graph and after that it will be an easy problem to deal with. I am not quite sure, how I will do it but I will appreciate some sources, wherein I can read about something similar.
  3. Are there any other tips, that I shall go by, for this project?

PS : By Navigation I mean, given the starting and end point, and considering the starting point to be the same as the current location of the device, it shall move to the final location on its own.

Thanks.

share|improve this question
2  
possible duplicate of Navigating for finding directions –  World Engineer Jan 23 '13 at 19:12
2  
Rather than reposting a (closed) question, it is better to fix the old one and ask for it to be reopened. –  MichaelT Jan 23 '13 at 19:18
2  
@WorldEngineer I am not sure that it is the same question. One wasn't even a real question, this one at least shows prior effort and a presents a problem. –  maple_shaft Jan 23 '13 at 19:24
    
@WorldEngineer The other one basically asks for the rudimentary information, and I agree that was not even a real question. This one relates to the implementation issue. Also, I have also voted for the other one to be closed, and I will be deleting that one itself in a couple of hours. –  Kraken Jan 23 '13 at 19:34
add comment

1 Answer

up vote 1 down vote accepted

For built environments you would probably store the walls as lines (ie. store the end point coordinates). Then finding a collision is just finding if the line of your path crosses any of the lines of the walls. Algorithms to check if/where 2d lines cross are very fast and easy

share|improve this answer
    
Becket So I store the walls as lines, i.e. using their end points, what about the rest of the space? Then I wont be using the 2D array for representing the data? But I still need to convert the final data set into graphs right? For me to be able to find a route between two nodes? –  Kraken Jan 23 '13 at 19:32
    
If you don't care about terrain (you don't have heights or water etc) then doing everything on a 2d plane by storing lines is easiest –  Martin Beckett Jan 23 '13 at 19:35
    
Becket Assuming for now that I dont have terrains, how exactly do you propose for me to represent the floor chart? I get that the walls could be saved using the end points, then I guess, I dont need to save anything else. Then how, given the start and end, do I navigate? –  Kraken Jan 23 '13 at 19:39
    
@Kraken By navigate do you mean "go forward 3 feet, turn clockwise 45 degrees, go forward 3 feet, ..." or do you mean "Go from room A to room B"? –  MichaelT Jan 23 '13 at 19:44
    
@MichaelT Go from A to B. i.e my device shall start from the starting point, considering it is the current position of the device, and it shall move to the final point. –  Kraken Jan 23 '13 at 19:46
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.