Navigation algorithm implementation in j2me for mobile devices

As part of my college project I'm developing a customized mobile navigation application. I'm using J2ME.

By customized I mean the application can be used in places only where the user wishes to use them. Now, the 'customized' area is my college premises. So if any student needs directions to reach his classroom or block he will be guided to that location.

I cannot use the google maps because the campus is not totally covered in them. So i take coordinates of all the blocks and roads and store in my landmarkstore and create a mini map of coordinates.

Now the real problem is 'How do i implement the navigation part of the application'? This is what is my current plan of action for the implementation.

I decided to use the Dijkstra's algorithm to find the shortest path. I'll just add the current position of the user into the graph and call it the source. The cost-adjac开发者_C百科ency matrix will be populated within the program.

Now the algorithm works and the shortest path is generated with the first instruction saying eg. Move 100mts due north.

The user proceeds as such but makes a mistake and goes in the wrong direction . How do I constantly check if the user is proceeding in the right direction? If i do check with his position every 10seconds and alert him if he is on the wrong course,(I dont know how to do this either! ie, checking if he is on the right course) and generate new directions again won't I be slowing the application down?

Is there a better way of implementing it?

PS: Please help me with how the coordinates must be stored in my database(landmarkstore) Should i store the coordinates for every small distance(eg. 5mts) or should i use a longer distance so that the number of nodes in the graph is reduced and the algorithm works faster.

First of all "being on the wrong course" can be easily detected : the length of the shortest path to the destination is increasing. Or if you have some "checkpoints" along your optimal path then the user is going away from the next checkpoint.

For the complexity don't use a point every 5mts or other distance : you need to have some main points in your map (each door, hallway crossing...) you can give you general direction. You can even imagine prec-omputing shortest path between each building and then inside each building ; your first need to leave the building to go to the other one.

Anyway once you have these main points you only need to add one point to you map (the user position) and connect it to the neighboring "main points".

How many nodes do you have in your graph for now ?

Basically the idea is the following one : given all the roads it is really easy to pre-compute the shortest path from any point of the road to any building. No need to do that for every road, only consider every intersection or building as a node in your graph. Then given a point on the road yon only have two possibilities to read a node : left or right. (This suppose of course that people stay of the road but can be easily adapted ;) ).

Now given a person position find the closest road and find the shortest path to these roads. You now have a few positions on different roads and it's easy to compute the shortest path to the destination. Since almost everything is pre-computing you an update your info multiple times per second.

You can give instruction to the person and if you notice that the distance to destination is increasing you can warn him he is going in the wrong direction.