Separating a walkable environment into layers

Arne Hillebrand; Marjan Van Den Akker; Roland Geraerts; Han Hoogeveen

doi:10.1145/2994258.2994271

Separating a walkable environment into layers

Arne Hillebrand^*, Marjan Van Den Akker, Roland Geraerts, Han Hoogeveen

^*Corresponding author for this work

Algorithms and Complexity

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

A multi-layered environment is a representation of the walkable environment in a 3D virtual environment that comprises a set of two-dimensional layers together with the locations where the different layers touch, which are called connections. This representation can be used for crowd simulations, e.g. to determine evacuation times in complex buildings, or for finding the shortest routes. The running times of these algorithms depend on the number of connections.

Finding an environment with the smallest number of connections, is an NP-Hard problem. Our first algorithm tackles this problem by using an integer linear program which is capable of finding the best possible solution, but naturally takes a long time. Hence, we provide two heuristics that search for multi-layered environments with a low number of connections. One algorithm uses local search to gradually improve the found solution. The other one, called the height heuristic, is very fast and gives good solutions in practical environments.

Original language	English
Title of host publication	Proceedings - Motion in Games 2016
Subtitle of host publication	9th International Conference on Motion in Games, MIG 2016
Editors	Stephen N. Spencer
Place of Publication	New York
Publisher	Association for Computing Machinery
Pages	101-106
Number of pages	6
ISBN (Print)	978-1-4503-4592-7
DOIs	https://doi.org/10.1145/2994258.2994271
Publication status	Published - 10 Oct 2016
Event	9th International Conference on Motion in Games, MIG 2016 - San Francisco, United States Duration: 10 Oct 2016 → 12 Oct 2016

Publication series

Name	Proceedings - Motion in Games 2016: 9th International Conference on Motion in Games, MIG 2016

Conference

Conference	9th International Conference on Motion in Games, MIG 2016
Country/Territory	United States
City	San Francisco
Period	10/10/16 → 12/10/16

Bibliographical note

Publisher Copyright:
© 2016 Copyright held by the owner/author(s).

Keywords

Multi-layered environment
Optimization

Access to Document

10.1145/2994258.2994271

Separating a walkable environment into layersFinal published version, 862 KBLicence: Taverne

Cite this

Hillebrand, A., Van Den Akker, M., Geraerts, R., & Hoogeveen, H. (2016). Separating a walkable environment into layers. In S. N. Spencer (Ed.), Proceedings - Motion in Games 2016: 9th International Conference on Motion in Games, MIG 2016 (pp. 101-106). Article 2994271 (Proceedings - Motion in Games 2016: 9th International Conference on Motion in Games, MIG 2016). Association for Computing Machinery. https://doi.org/10.1145/2994258.2994271

Hillebrand, Arne ; Van Den Akker, Marjan ; Geraerts, Roland et al. / Separating a walkable environment into layers. Proceedings - Motion in Games 2016: 9th International Conference on Motion in Games, MIG 2016. editor / Stephen N. Spencer. New York : Association for Computing Machinery, 2016. pp. 101-106 (Proceedings - Motion in Games 2016: 9th International Conference on Motion in Games, MIG 2016).

@inproceedings{d5337a884a2a47968d875ee395a3ac72,

title = "Separating a walkable environment into layers",

abstract = "A multi-layered environment is a representation of the walkable environment in a 3D virtual environment that comprises a set of two-dimensional layers together with the locations where the different layers touch, which are called connections. This representation can be used for crowd simulations, e.g. to determine evacuation times in complex buildings, or for finding the shortest routes. The running times of these algorithms depend on the number of connections.Finding an environment with the smallest number of connections, is an NP-Hard problem. Our first algorithm tackles this problem by using an integer linear program which is capable of finding the best possible solution, but naturally takes a long time. Hence, we provide two heuristics that search for multi-layered environments with a low number of connections. One algorithm uses local search to gradually improve the found solution. The other one, called the height heuristic, is very fast and gives good solutions in practical environments.",

keywords = "Multi-layered environment, Optimization",

author = "Arne Hillebrand and {Van Den Akker}, Marjan and Roland Geraerts and Han Hoogeveen",

note = "Publisher Copyright: {\textcopyright} 2016 Copyright held by the owner/author(s).; 9th International Conference on Motion in Games, MIG 2016 ; Conference date: 10-10-2016 Through 12-10-2016",

year = "2016",

month = oct,

day = "10",

doi = "10.1145/2994258.2994271",

language = "English",

isbn = "978-1-4503-4592-7",

series = "Proceedings - Motion in Games 2016: 9th International Conference on Motion in Games, MIG 2016",

publisher = "Association for Computing Machinery",

pages = "101--106",

editor = "Spencer, {Stephen N.}",

booktitle = "Proceedings - Motion in Games 2016",

address = "United States",

}

Hillebrand, A, Van Den Akker, M , Geraerts, R & Hoogeveen, H 2016, Separating a walkable environment into layers. in SN Spencer (ed.), Proceedings - Motion in Games 2016: 9th International Conference on Motion in Games, MIG 2016., 2994271, Proceedings - Motion in Games 2016: 9th International Conference on Motion in Games, MIG 2016, Association for Computing Machinery, New York, pp. 101-106, 9th International Conference on Motion in Games, MIG 2016, San Francisco, United States, 10/10/16. https://doi.org/10.1145/2994258.2994271

Separating a walkable environment into layers. / Hillebrand, Arne; Van Den Akker, Marjan ; Geraerts, Roland et al.
Proceedings - Motion in Games 2016: 9th International Conference on Motion in Games, MIG 2016. ed. / Stephen N. Spencer. New York: Association for Computing Machinery, 2016. p. 101-106 2994271 (Proceedings - Motion in Games 2016: 9th International Conference on Motion in Games, MIG 2016).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Separating a walkable environment into layers

AU - Hillebrand, Arne

AU - Van Den Akker, Marjan

AU - Geraerts, Roland

AU - Hoogeveen, Han

PY - 2016/10/10

Y1 - 2016/10/10

N2 - A multi-layered environment is a representation of the walkable environment in a 3D virtual environment that comprises a set of two-dimensional layers together with the locations where the different layers touch, which are called connections. This representation can be used for crowd simulations, e.g. to determine evacuation times in complex buildings, or for finding the shortest routes. The running times of these algorithms depend on the number of connections.Finding an environment with the smallest number of connections, is an NP-Hard problem. Our first algorithm tackles this problem by using an integer linear program which is capable of finding the best possible solution, but naturally takes a long time. Hence, we provide two heuristics that search for multi-layered environments with a low number of connections. One algorithm uses local search to gradually improve the found solution. The other one, called the height heuristic, is very fast and gives good solutions in practical environments.

AB - A multi-layered environment is a representation of the walkable environment in a 3D virtual environment that comprises a set of two-dimensional layers together with the locations where the different layers touch, which are called connections. This representation can be used for crowd simulations, e.g. to determine evacuation times in complex buildings, or for finding the shortest routes. The running times of these algorithms depend on the number of connections.Finding an environment with the smallest number of connections, is an NP-Hard problem. Our first algorithm tackles this problem by using an integer linear program which is capable of finding the best possible solution, but naturally takes a long time. Hence, we provide two heuristics that search for multi-layered environments with a low number of connections. One algorithm uses local search to gradually improve the found solution. The other one, called the height heuristic, is very fast and gives good solutions in practical environments.

KW - Multi-layered environment

KW - Optimization

UR - http://www.scopus.com/inward/record.url?scp=84994904840&partnerID=8YFLogxK

U2 - 10.1145/2994258.2994271

DO - 10.1145/2994258.2994271

M3 - Conference contribution

AN - SCOPUS:84994904840

SN - 978-1-4503-4592-7

T3 - Proceedings - Motion in Games 2016: 9th International Conference on Motion in Games, MIG 2016

SP - 101

EP - 106

BT - Proceedings - Motion in Games 2016

A2 - Spencer, Stephen N.

PB - Association for Computing Machinery

CY - New York

T2 - 9th International Conference on Motion in Games, MIG 2016

Y2 - 10 October 2016 through 12 October 2016

ER -

Hillebrand A, Van Den Akker M , Geraerts R , Hoogeveen H. Separating a walkable environment into layers. In Spencer SN, editor, Proceedings - Motion in Games 2016: 9th International Conference on Motion in Games, MIG 2016. New York: Association for Computing Machinery. 2016. p. 101-106. 2994271. (Proceedings - Motion in Games 2016: 9th International Conference on Motion in Games, MIG 2016). doi: 10.1145/2994258.2994271

Separating a walkable environment into layers

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this