Overview

Bound by set constraints,
Of logic and of value,
Sworn to solve the goal

Solver-based methods are a method of using algorithms to solve specific problems using constraints solvers, to help generate a set of solutions or a single best solution to a problem.[1]

Solver based methods can be implemented in many different ways, such as mathematically or logically using logic based languages, such as ASP (Answer Set Programming).[1][2]

“Constraint Programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it.” [E. Freuder][6]

Constraint Solvers

Constraint Solvers are used to constraint the limits of RNG (random number generation) and give logic to it so the PCG generates a desired result.[3]

You have some known values and a problem, you have a near infinite set of answers, you work with a set of constraints to reduce that to a single solution or a set of good solutions.

e.g. I want to place 10 towns over the map, but they all must be 5km away from each other AND they must each be 2km from a water source AND ...

Method Uses

A list of different uses for Solver Based Methods:

IK solving

IK (Inverse kinematics) solving is a way of figuring out the location of a joint between 2 other joints which are bound by constraints such as limb segment lengths and joint bending/twisting constraints.[2]

Level generation

Level generation can use constraint solvers for good number of reasons such as programming in hard rules and constraints that the generator needs to follow to create a playable level.[3][4]

References

[1] G. N. Yannakakis and J. Togelius, "Artificial Intelligence and Games". Springer, 2018.
[2] K. Compton, "Practical Procedural Generation for Everyone", YouTube, 2019. [Online]. Available: https://www.youtube.com/watch?v=WumyfLEa6bU&feature=youtu.be&t=1436. [Accessed: 15- Feb- 2019].
[3] A. Smith, M. Nelson and M. Mateas, "LUDOCORE: A logical game engine for modeling videogames", Proceedings of the 2010 IEEE Conference on Computational Intelligence and Games, p. Chapter 8, 2010. Available: 10.1109/itw.2010.5593368 [Accessed 15 February 2019].
[4] G. Smith, J. Whitehead and M. Mateas, "Tanagra", Proceedings of the Fifth International Conference on the Foundations of Digital Games - FDG '10, 2010. Available: 10.1145/1822348.1822376 [Accessed 15 February 2019].
[5] K. Compton, "Tumblr", Galaxykate0.tumblr.com, 2019. [Online]. Available: http://galaxykate0.tumblr.com/post/139774965871/so-you-want-to-build-a-generator. [Accessed: 15- Feb- 2019].
[6] "Constraint Solving", Constraintsolving.com, 2019. [Online]. Available: http://www.constraintsolving.com/. [Accessed: 15- Feb- 2019].