Мне эта многоходовка представляется так:
1. Плоскость с препятствиями делится на прямоугольники (тут тоже стоит подобрать алгоритм)
2. http://ru.wikipedia.org/wiki/Упаковка_шаров
Про производительность JS не скажу, зависит от количества шаров и выбранных алгоритмов.
Как вариант, можно работать с урлом такого вида site.com/id/pretty-url
, и попросту игнорировать часть "pretty-url". Посмотрите по новостным сайтам - некоторые именно так работают.
Upd. Не заметил ваш комментарий выше. Тогда да, индексирование по полю урла будет работать сносно.