Про собственный сервер в вопросе ничего не было 
Собственный сервер есть у cloudmade, у них же через api брать и построенные маршруты - пешие, велосипедные, на машине ближайший или быстрейший. 
Ок. +1 за XML.
Указываем точку старта. Указываем точку финиша. Программа загружает прямоугольник с углами в этих точках - это для определения самого короткого маршрута. Для самого быстрого - да, надо ещё больше загружать, т.к. быстрая дорога может идти за пределами этого прямоугольника. Надо считать, но вроде как эту область тоже можно вычислить формулой, если за время брать время короткого маршрута и предполагать, что в области, не попавшей в прямоугольник находится какая-то быстрая дорога (магистраль). Т.е. по предположению о максимально удалённом расположении этой быстрой дороги можно получить больший прямоугольник.
Как-то так.
Значит -1 за XML.
Вроде как есть же аналоги. Не знаешь, как они вышли из положения?
Нет, я уже сказал, что в первую очередь хочу просто попробовать покодить под мобильный девайс. На днях всё поставил и … первая моя прога скомпилировать без ошибок. :)) Так что желание пока есть.
А существующие есть?
Я этот момент прогулял в универе - графы строить - это большие расчёты?
Есть такие более-менее документированные ресурсы?
Попробуй прочитать остальную часть моего сообщения. :-\
Real 3L0,
я бы не советовал сразу браться за ВСЁ.
Начать стоило бы с простого отображения карты (хотя бы мапниковских тайлов) и местоположения, записи трека.
Если получится - можно попытаться сделать ВЕДЕНИЕ по маршруту, сам маршрут брать готовый с того же клаудмейда.
И только потом стоит задуматься о собственной маршрутизации
Благодарю. Интересно.
Но для WM у них С++ и нет поиска по карте.
Именно так я и хотел! 
Но когда стал разбираться в теме, то и возникли первоначальные вопросы. И не в последнюю очередь я задаю эти вопросы с расчётом на то, чтобы в будущем (если не заброшу это дело) мне не прешлось всё переписывать.
Вот сейчас ты говоришь, что надо использовать тайлы. Это картинки. С ними всё ясно. А информацию по контенту этих картинок где потом брать? Отдельно грузить? (Сразу скажу, что это вопрос не из серии “чо ты мне фигню какую-то предлагаешь”, а для того, чтобы я более полно разобрался в вопросе - может всё и не так страшно. )
Т.е. получается, что всё такие отдельно. Ладно, пусть так.
Да, точно. Могу наверное попробовать сконвертить OsmTracker c VbNet на C# и перепрофилировать. Кстати, интересно, а Mono умеет для CF комплить? Или вообще без разницы на каком фреймвоке делать?
Сорь, но ей богу - тебя в гугле забанили что ли???
Гы. Но именно с изучения кода OsmTracker’а я и хотел начать.
C# - т.е. только под WinMobile, у которого сейчас очень туманные перспективы?
Это всё ещё вилами на воде писано.
Ну, если прога будет совместима с Mono, тогда вполне возможно будет идти на многих других платформах, например Maemo или даже Openmoko.
Ну, это не совсем так. Не нужна полная карта России, чтобы проложить маршрут в ближайшую деревню, а чтобы доехать в другой конец России, скорее всего понадобится карта магистралей и карты местных дорог точек отправления и прибытия. Для этого нужен грамотный алгоритм отсечения (чтобы знать, какой фрагмент нужен, а какой нет).
Как Вы понимаете, в общем случае это не работает. Кратчайший из нарисованных маршрутов имеет полное право вылезти за скачанный прямоугольник. (это так, к слову)
Это не то что в общем, это в половине случаев не работает.
Реки и ж/д никто не отменял
Т.е. нужен, как минимум, материк? 
Ivan Komarov, нужен связный_граф
Много знаете устройств на Maemo и Openmoko?
На чем писать - выбор несомненно автора, однако будет досадно, если хороший проект не будет популярен из-за плохой поддержки устройств.