Игры с Open Street Map

Какое-то время назад мне пришла в голову мысль о том, что можно использовать данные из базы Open Street Map в играх, например при создании уровней. На первый взгляд они для этого хорошо подходят — бесплатные, с открытой лицензией, подробные.
При ближайшем рассмотрении обнаружились некоторые нюансы.

Open Street Map

Для тех, кто ни разу раньше с ними не сталкивались, коротко расскажу:  карты от Open Street Map (далее OSM) это векторные однослойные карты с большим количеством объектов, которые создаются сообществом энтузиастов по принципу wiki. Их может использовать в целом кто угодно и зачем угодно, например для создания приложений для телефона (мой любимый maps.me сделан на основе OSM, также на них кажется перешли Pokemon Go).

Есть несколько способов скачать карту. Самый простой — кнопка Export на сайте openstreetmap.org,
но так можно выкачать только небольшие области (до 0.5 градуса).  

Более универсальный способ — запрос с помощью специального языка, например: 

wget -O test.osm «https://overpass.kumi.systems/api/interpreter?data=node(51.249,7.148,51.251,7.152);out;»

По этой команде все объекты из указанных границ (широта, долгота) будут сохранены в файл test.osm. Если задать слишком большие границы, то можно получить ошибку или таймаут. 

При помощи языка запросов можно более точно указывать и фильтровать то, чтот хотите скачать. Подробнее о нем можно прочесть в справке. Данные OSM могут храниться как в виде обычного XML, так и в своем бинарном формате. Для простоты рассмотрим XML (*.osm).

Карта состоит из 3 видов объектов. 

1. node — точка
   Точки перечисляются в начале файла. Они могут как сами по себе описывать какой-нибудь точечный объект, так и входить в состав более сложного (например угол здания).
   Пример описания точки:
   <node id='223641' timestamp='2016-04-02T08:46:58Z' uid='39040' user='Dinamik' visible='true' version='6' changeset='38244341' lat='59.9440931' lon='30.3055493'>
<tag k='bus' v='yes' />
<tag k='name' v='Биржевая площадь' />
<tag k='name:ru' v='Биржевая площадь' />
<tag k='public_transport' v='stop_position' />
<tag k='trolleybus' v='yes' />

   </node>


   Как и у остальных объектов, у точек есть идентификатор id. Для нас также важны поля lat и long, в которых хранятся, как это ни удивительно, широта с долготой. Также у этой точки указаны теги, в данном случае это остановка толлейбуса. 
2. way — контур
   Из точек можно собирать контуры, которые могу быть замкнутыми и незамкнутыми. Пример контура:
   <way id='407178685' timestamp='2018-07-29T18:37:38Z' uid='3846961' user='mini-me' visible='true' version='2' changeset='61171180'>
<nd ref='2537529226' />
<nd ref='4092138237' />
<nd ref='5794276614' />
<nd ref='5794276616' />
<nd ref='4092138238' />
<nd ref='4092138240' />
<nd ref='4092127943' />
<tag k='highway' v='footway' />
</way>
   
   Как можно видеть, основное в описании контура — последовательность точек, из которых он состоит. Контуры используются для описания протяженный объектов, например дорог или стен домов.
3. relation — отношение
   Отношение это объединение любого количества контуров и точек. Пример:
   <relation id='455384' timestamp='2017-03-27T10:19:06Z' uid='29272' user='putnik' visible='true' version='5' changeset='47197397'>
<member type='way' ref='52829137' role='outer' />
<member type='way' ref='28566723' role='inner' />
<tag k='addr:housenumber' v='5' />
<tag k='addr:street' v='Менделеевская линия' />
<tag k='building' v='university' />
<tag k='building:levels' v='3' />
<tag k='name' v='Исторический факультет СПбГУ' />
<tag k='old_name' v='Гостиный двор Новобиржевой' />
<tag k='type' v='multipolygon' />
<tag k='url' v='http://www.history.pu.ru/' />
<tag k='wikidata' v='Q4323247' />
<tag k='wikipedia' v='ru:Новобиржевой Гостиный двор' />
</relation>

В данном случае отношением описывается здание со внутренним двором, состоящее из внешнего и внутреннего контура, на что указывает тег multipoilygon и теги inner и outer у контуров.

Итак, OSM предоставляет нам данные для карты нашей игры. Первым делом я захотел эту карту нарисовать, и тут встретился нюанс номер 1. 

Отрисовка

  Как можно заметить, нам доступны границы и контуры различных областей, а чтобы нарисовать их заполненными (например используя OpenGL) понадобятся треугольники, из которых они состоят. 

Если вы делаете рогалик, то можете с этим не связываться, а просто проверить при загрузке каждую клету на проходимость. 

Самый простой алгоритм для проверки принадлежности точки к многоугольнику, который мне удалось найти:

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
  int i, j, c = 0;
  for (i = 0, j = nvert-1; i < nvert; j = i++) {
    if ( ((verty[i]>testy) != (verty[j]>testy)) &&
	 (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
       c = !c;
  }
  return c;
}

Однако хотелось бы не быть привязанными к прямоугольной сетке, а использовать точные области. Для этого придется разбить их на треугольники.

Для этого я использовал библиотеку libtess2 (https://github.com/memononen/libtess2), которая, помимо этого, позволяет производить булевые операции с многоугольниками, что понадобится нам далее.

После того как мы получим набор треугольников, можно их наконец нарисовать:

Тут можно споткнуться об нюанс номер 2: если со зданиями, описанными одним контуром, никаких проблем нет, то с отношениями все может быть сложно. Никаких особенных требований к ним не предъявляется, они могут состоять из любого количества контуров с произвольной ориентацией. За этим придется следить и переделывать под ваши нужды. 

Заодно загрузим и нарисуем дорожную сеть. Во-первых, мы можем сделать по ней поиск пути и использовать для перемещения NPC. Во-вторых,  она укажет проходы через здания (арки во дворы). Для того чтобы сделать  стены в нужных местах проходимыми, можно например достроить вокруг путей прямоугольники, и вычесть их из зданий.

Здесь арки успешно пробились, однако дом нависал над тротуатом, и возник странный эффект.

Так как я выбрал в качестве примера карту Васильевского острова, то, кроме домов и улиц, приедставляли интерес контуры берегов.  Чтобы можно было перебраться на соседний остров, понадобилось проделать в них дырки, и тут возник нюанс номер 3.

Когда я захотел удалить часть контура, выяснилось, что эта часть входит в другой, больший контур. Следовало перераспределить вершины между 2 соседними контурами и удалить ненужные. «Никто же не будет делать это в блокноте,» — подумал я. «Надо найти редактор». 

Насколько я понял, самым актуальным и удобным редактором для OSM является JOSM . И вроде бы с ним все нормально, пока мы не пытаемся что-то редактировать. Проблема в том, что при создании новых объектов редактор не присваивает им id, а ждет отправки правок на сервер (wiki-карта, помните?), который выдает идентификаторы согласованно с остальной картой и остальными участниками.

Поскольку у нас другая задача, правок на сервер мы отправлять не хотим, и что с этим делать я пока не придумал (кроме как писать свой редактор, но это наверное неоптимально).  

Пришлось ковырять дырки в блокноте.

Масштабы

Для того чтобы добавить на карту игрока, движение и столкновение со стенами я использовал свой любимый box2d.  Реальная карта подталкивала к реальной скорости перемещения, но ходить с пешеходной скоростью довольно скучно, особенно если пункты назначения далеко. Поэтому для героя была собрана тачила (с помощью реверс-порта машинки из OpenAI gym).

Наполнение

Что касается пунктов назначения, то можно продолжить тренд использования реальных данных и взять, например, список адресов репрессированных. Тогда тачка превращается в воронок, герой в следователя, а игра в спинофф Papers, please.

Другой вариант — сделать точками интереса те точки карты, у которых есть в тегах memorial или historic. Их в данном случае  немало, хотя они не исчерывающи и довольно неравномерно распределены.

Третий вариант — есть уже готовые списки КП для городского ориентирования от «Бегущего города» в формате KML, которые содержат кучу странных «достопримечательностей».

Итоги

Результат всех этих экспериментов можно найти здесь:

https://github.com/aash29/GLMap/tree/release

«Релиз» для тех, кто захочет погонять по пустынным улицам Васильевского острова.

https://github.com/aash29/GLMap/releases/download/0.1/glmap.zip

Управление:

WASD — движение

Колесо мыши — приближение/ отдаление

Enter — выйти/сесть в машину

Надеюсь, что-нибудь из этого окажется вам полезным, спасибо что прочли.