Computational Network Design from Functional Specifications
Authors:
- Chi-Han PengCPChi-Han Peng
- Niloy J. MitraNMNiloy J. Mitra
- Fan BaoFBFan Bao
- Dong-Ming YanDYDong-Ming Yan
- Peter WonkaPWPeter Wonka
Preprint
Abstract
Connectivity and layout of underlying networks largely determine the behavior of many environments. For example, transportation networks determine the flow of traffic in cities, or maps determine the difficulty and flow in games. Designing such networks from scratch is challenging as even local network changes can have large global effects. We investigate how to computationally create networks starting from {\em only} high-level functional specifications. Such specifications can be in the form of network density, travel time versus network length, traffic type, destination locations, etc. We propose an integer programming-based approach that guarantees that the resultant networks are valid by fulfilling all specified hard constraints, and score favorably in terms of the objective function. We evaluate our algorithm in three different design settings (i.e., street layout, floorplanning, and game level design) and demonstrate, for the first time, that diverse networks can emerge purely from high-level functional specifications.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- What Makes London Work Like London?Computer Graphics Forum, 2014
- Game level layout from design specificationComputer Graphics Forum, 2014
- Authoring Hierarchical Road NetworksComputer Graphics Forum, 2011
- Global optimization method for mixed transportation network design problem: A mixed-integer linear programming approachTransportation Research Part B: Methodological, 2011
- Procedural Generation of RoadsComputer Graphics Forum, 2010
- Interactive Geometric Simulation of 4D CitiesComputer Graphics Forum, 2009
- Interactive example-based urban layout synthesisACM Transactions on Graphics, 2008
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphsRandom Structures & Algorithms, 2006
- Street Standards and the Shaping of SuburbiaJournal of the American Planning Association, 1995
- Snakes: Active contour modelsInternational Journal of Computer Vision, 1988