I'm writing a sample game where a block falls down forever, and you need to steer it from side to side. If you hit the walls, you lose. I'm trying to randomly and continually generate the level so there's always a way through, and so the path gets progressively narrower.
# #
# #
# ##
# ###
# ####
# #####
## #####
## #####
## ####
### ####
### ###
#### ###
#### ###
### ###
### ###
## ####
## ####
## #####
## #####
## ######
## ######
## ######
## ######
My current approach is to have an array of possible paths, then I randomly select a row. The problem is that the path is not smooth, and at times, it becomes impossible:
# #
# ####
# #####
### ###
## #####
### ####
# ###
## #####
#### ### <--- can't get through here
## ####
#### ###
### ###
# ##
## ######
## #####
## ######
## #####
## #####
## ####
## ####
# #
### ###
## ###### <--- or here
# #
## ######
## ######
What class of algorithms would help me get started with this?
Here the basis of a simple algorithm which can be improved to get a more challenging and interesting game. There is no IA here.
It just generates paths which can always be possible thanks to the older path.
The basic idea is to stick with an index which will be the middle of the path.
There you randomly stay or move this middle index to the right or left.
I have chosen in my implementation to randomly get the path narrower. One possible improvement is to make deeper and smarter moves by taking into account the wideness in such a way to have coherent paths (can do it if needed).
// path is a vector of booleans
// wideness tells how narrow the path is
// middle represents the middle of the path
while wideness > 0
{
thicken wideness sometimes
move middle to the right, left, or do not move it
print the path
}
You can have a look at the Live C++ code and algorithm here.
Result can look like this :
|# #########|
|## ########|
|## ########|
|### #######|
|#### ######|
|### #######|
|### #######|
|#### ######|
|##### #####|
|##### #####|
|##### #####|
|#### ######|
|##### #####|
|###### ####|
|####### ###|
|####### #####|
|######## ####|
|######### ###|
|######## ####|
|######### ###|
|######## ####|
|######### ###|
|######### ###|
|######## ####|
|######### ###|
|######### ###|
|########## ##|
|########### #|
|########### #|
|########### #|
|########### #|
|########### #|
|########## ##|
|########## ##|
|########## ##|
|########### #|
|########### #|
|########### #|
|########### #|
|########### #|
|########### #|
|########### #|
|########### #|
|########## ##|
|######### ###|
|######### ###|
|######### ###|
|########## ##|
|########## ##|
|########## ##|
|######### ###|
|######## ####|
|####### #####|
|###### ######|
|####### #####|
|######## ####|
|######### ###|
|######## ####|
|######### ###|
|######### ###|
|########## ##|
|########### #|
|########## ##|
|########## ##|
|########### #|
|########## ##|
|######### ###|
|########## ##|
|########## ##|
|########## ##|
|########## ##|
|######### ###|
|########## ##|
|########### #|
|########## ##|
|########### #|
|########### #|
|########### #|
|########## ##|
|########### #|
|########## ##|
|########### #|
|########### #|
|########### #|
|########### #|
|########### #|
|########### #|
|########## ##|
|########### #|
|########### #|
|########## ##|
|######### ###|
|######### ###|
|########## ##|
|######### ###|
|########## ##|
|########## ####|
|########## ####|
|######### #####|
|######## ######|
|######### #####|
|######### #####|
|######## ######|
|######### #####|
|########## ####|
|######### #####|
|######## ######|
|######## ######|
|######## ######|
|######### #####|
|######### #####|
|########## ####|
|######### #####|
|########## ####|
|########## ####|