Drawing paths, finding paths and giving instructions

Mon, 02/07/2011 - 19:47

I'm currently developing a kiosk application which shows a map of the place where the multimedia kiosk is located and gives directions to the user when a destination is selected. Right now this application is being developed in WPF, though it could be web based also. In the kiosk application I created an invisible grid that lies on top of the map. This grid has some marked cells that are the ones where one could walk through in the real map, so when a destination is picked, the application will find and draw the shortest walkable path from the kiosk current location (previously marked in the grid) to the destination (also marked in the grid). This was achieved by using a well known path finding algorithm called A* (A star). This algorithm consists in assigning cost numbers to the cells, indicating the effort to get to that cell from the starting point and an estimation of how hard would it be to get to the destination point from that cell, so, the shortest path is constructed by selecting the cells with the lesser cost. 

Once the path has been found I would have a list with the cells that build it, so I simply draw a little dot in each cell showing the path that should be taken to get to the desired place. Now, another requirement is to give instructions of how to get there. I'm still working on this, but I started by identifying how many grid cells have been "walked" in a straight line which I can do analyzing the path cell by cell. Taking the position of the first cell and the position of the current analyzed one I can get an imaginary straight line and see if each cell from the starting one till the current one touch the line. If every cell walked till this point touches the line I will assume that the path is in a straight line so I will just count how many cells until I find a turn and then inform the user how long will he have to walk in a straight line. 
When I find that there's no more straight line I start a new line taking as the first point the first point not aligned with the previous line and inform to turn. Where to turn? I designed a simple way to know in what direction I was going and which direction did I just take assigning cardinal points taking the first and the last point of the line. First I check how different is the slope of the previous line compared to the current one.  For example, if the current slope is negative and direction is NE (northeast), and the previous slope was positive and the direction was SE (southeast) I indicate to turn left.
This part is still under heavy testing and I intend also to assign a property to each cell that contains information of where in the place it is located, such as corridor, hall, fountain, etc. so I can add further information to the user of where will he be going straight or turning.

{syntaxhighlighter brush:csharp; } private bool isInLine(IList l) { _lineStart = l[0]; _lineEnd = l[l.Count - 1]; bool isStraightLine = true; int _deltaX = _lineEnd.X - _lineStart.X; int _deltaY = (_lineEnd.Y - _lineStart.Y); if (_deltaX == 0) { _a = 1000; return true; } _a = (decimal) _deltaY / _deltaX; int j=0; while (isStraightLine && j < l.Count) { int yPos = (l[j].Y - _lineStart.Y) * 5; decimal yPosLine = (l[j].X - _lineStart.X) * 5 * _a; //isStraightLine = (yPos + 3 >= yPosLine && yPos - 3 <= yPosLine); if (Math.Abs(_a)<=1) isStraightLine = Math.Abs(yPos - yPosLine) < 3; else isStraightLine = Math.Abs(Math.Abs((yPosLine/_a)) - Math.Abs(l[j].X - _lineStart.X)) < 10; j++; } DetermineDirection(_deltaX, _deltaY); return isStraightLine; } {/syntaxhighlighter}

On the other hand, I have been also working in the map path designer. I am developing it in an ASP.Net MVC 2 application, the idea is that the maps can be managed remotely, even from the Internet. This application lets you upload an image with the map of your Hospital, Mall, University, etc and then lets you mark the kiosk position and the position of the points of interest (these would be the selectable destinations for the final user). And finally the administrator can paint the walkable path on top of the map. 
To do all this stuff I did something similar to what I did in WPF. I showed the image and on top of it I drew an invisible table where each table cell represents a walkable cell. I let the user click on each cell to mark it as walkable, and also I use a javascript algorithm to let the user draw straight lines to simplify the task.

The javascript code to draw a line:

{syntaxhighlighter brush:javascript; } var nextCell; nextCell = document.getElementById("tblGrid").rows[firstLinePointY].cells[firstLinePointX]; nextCell.className = "selectedCell"; nextCell.selected = true; var l = new line(firstLinePointX, firstLinePointY, posX, posY); inc = 1; if (Math.abs(l.a) <= 1) { if (firstLinePointX > posX) inc = -1; for (i = 0; i != posX - firstLinePointX + inc; i += inc) { l.xval = i * cellsize; nextCell = document.getElementById("tblGrid").rows[firstLinePointY + Math.ceil(l.f() / cellsize)].cells[i + firstLinePointX]; if (undraw) { nextCell.className = (nextCell.selected) ? "selectedCell" : "cell"; } else { if (drawingLine) { nextCell.className = "cellHover"; } else { nextCell.className = "selectedCell"; nextCell.selected = true; } } } } else { if (firstLinePointY > posY) inc = -1; for (i = 0; i != posY - firstLinePointY + inc; i += inc) { l.yval = i * cellsize; nextCell = document.getElementById("tblGrid").rows[firstLinePointY + i].cells[firstLinePointX + Math.ceil(l.xfromy() / cellsize)]; if (undraw) { nextCell.className = (nextCell.selected) ? "selectedCell" : "cell"; } else { if (drawingLine) { nextCell.className = "cellHover"; } else { nextCell.className = "selectedCell"; nextCell.selected = true; } } } } {/syntaxhighlighter}


I'll keep you posted with the news of how is all this interesting solution evolving.



.Net Developer
I'm an enthusiastic analyst and developer who is always up to new challenges. I like to keep up with the continuously changing software development technologies and paradigms. I'm well trained in...