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.


  • 2
    possible duplicate of Navigating for finding directions
    – user28988
    Commented Jan 23, 2013 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.
    – user40980
    Commented Jan 23, 2013 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
    Commented Jan 23, 2013 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
    Commented Jan 23, 2013 at 19:34

1 Answer 1


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

  • 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
    Commented Jan 23, 2013 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 Commented Jan 23, 2013 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
    Commented Jan 23, 2013 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"?
    – user40980
    Commented Jan 23, 2013 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
    Commented Jan 23, 2013 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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