This is part four in a series of tutorials on procedural generation with Rust.
- Procedural level generation with Rust
- Drawing tile maps with Rust and Cairo
- Procedural level generation using Binary Space Partitioning in Rust
- Use prebuilt rooms with Rust macros (this one)
More interesting rooms
So far, the levels we're generating have completely empty rectangular rooms, which would make for a pretty boring game. In this tutorial, we'll update the room generation so it can also pick from a selection of pre-built room patterns as well as create the standard empty room.
What we'll cover:
- Update room to save layout and generate empty room
- Update level::add_room to add the tiles set in the room, not just walkable
- Update bsp: create vec of prebuilt rooms, pass iter to place_rooms
vec shuffle or add multiple
pick from vec rather than consume - Add macro
Code from this article can be found on Github.
Room layout
First of all, we need to change the Room struct so it contains its' own layout: when drawing the room, we'll use this layout instead of filling in a rectangle. The layout attribute will hold a two-dimensional vector of tiles, which means we'll no long be able to derive the Copy trait, since vector data lives on the heap and we can't move that around.
// room.rs
use level::Tile;
#[derive(Debug, Clone, Copy, Serialize)]
pub struct Point {
pub x: i32,
pub y: i32
}
// remove Copy
#[derive(Clone, Serialize)]
pub struct Room {
pub x: i32,
pub y: i32,
pub x2: i32,
pub y2: i32,
pub width: i32,
pub height: i32,
pub centre: Point,
pub layout: Vec<Vec<Tile>> // new layout field
}
impl Room {
pub fn new(x: i32, y: i32, width: i32, height: i32, layout: Option<Vec<Vec<Tile>>>) -> Self {
let tiles = match layout {
Some(tiles) => tiles,
None => {
let mut board = vec![];
for _ in 0..height {
let row = vec![Tile::Walkable; width as usize];
board.push(row);
}
board
}
};
Room {
x,
y,
x2: x + width,
y2: y + height,
width,
height,
centre: Point {
x: x + (width / 2),
y: y + (height / 2)
},
layout: tiles
}
}
pub fn intersects(&self, other: &Self) -> bool {
self.x <= other.x2 && self.x2 >= other.x && self.y <= other.y2 && self.y2 >= other.y
}
}In the new function, we now take an optional 2D vector of tiles; if one is provided, we use that as the layout, and if not, then we create a new 2D vector with the provided width and height. The None branch is very similar to the code currently in Level::new, except we add walkable tiles rather than empty ones for a room.
If you try to run the project now with cargo run, you'll see loads of errors since we've change the signature of new - we need to update RoomsCorridors::place_rooms:
// roomscorridors.rs
impl RoomsCorridors {
...
pub fn place_rooms(&mut self, rng: &mut StdRng) {
...
if y + height > self.level.height {
y = self.level.height - height;
}
let mut collides = false;
let room = Room::new(x, y, width, height, None); // Add 'None'
...and Leaf::create_rooms, Bsp::horz_corridor and Bsp::vert_corridor:
// bsp.rs
...
impl Leaf {
fn create_rooms(&mut self, rng: &mut StdRng) {
...
if self.is_leaf() {
let width = rng.gen_range(min_room_width, self.width);
let height = rng.gen_range(min_room_height, self.height);
let x = rng.gen_range(0, self.width - width);
let y = rng.gen_range(0, self.height - height);
self.room = Some(Room::new(x + self.x, y + self.y, width, height, None));
}
...
}
}
fn horz_corridor(start_x: i32, start_y: i32, end_x: i32) -> Room {
Room::new(start_x, start_y, (end_x - start_x) + 1, 1)
}
fn vert_corridor(start_x: i32, start_y: i32, end_y: i32) -> Room {
Room::new(start_x, start_y, 1, end_y - start_y)
}You'll also notice that we have a lot of errors about moving out of borrowed content where we try to pass around a room belonging to a Leaf, for instance in Leaf::get_room - this is because the Room struct no longer implements Copy. The simplest fix is to clone the room to create a new version when we need to move it; another way would be to pass references to the room along with guaranteeing the lifetimes. Let's just clone it:
// bsp.rs
...
impl Leaf {
...
fn get_room(&self) -> Option<Room> {
if self.is_leaf() {
return self.room.clone();
}
...
}
// roomscorridors.rs
...
impl RoomsCorridors {
...
fn place_corridors(&mut self, rng: &mut StdRng) {
for i in 0..(self.level.rooms.len() - 1) {
let room = self.level.rooms[i].clone();
let other = self.level.rooms[i + 1].clone();
...Cloning means we're creating a new object every time rather than using a reference - this will use up more memory, but is simpler to write and reason about than using lifetimes. This is a nice optimisation opportunity!
Next, we need to update Level::add_room: at the moment, we're just adding walkable tiles in a rectangle the size of the room, so instead we need to use the tiles provided by the preset room.
// level.rs
// add Copy trait
#[derive(Clone, Copy)]
pub enum Tile {
Empty,
Walkable
}
...
impl Level {
pub fn add_room(&mut self, room: &Room) {
for row in 0..room.layout.len() {
for col in 0..room.layout[row].len() {
let y = room.y as usize + row;
let x = room.x as usize + col;
self.board[y][x] = room.layout[row][col];
}
}
self.rooms.push(room.clone());
}
...Add the Copy trait to the Tile enum so we can copy the layout from the existing room over to the level's board; in add_room we just loop through every tile in the existing room and add it to the level. This allows us to be flexible in the future - if we wanted to add different types of tiles, the level will happily add them to the board without us having to update add_room.
Add prebuilt rooms
Now we just need a way to use the prebuilt rooms into our level. In bsp.rs, we'll create a couple of rooms, add them to a vector then pass that to create_rooms:
// bsp.rs
use level::{ Level,Tile }; // import Tile from level as well
...
impl BspLevel {
...
fn place_rooms(&mut self, rng: &mut StdRng) {
let prebuilt = vec![
vec![Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable],
vec![Tile::Empty, Tile::Empty, Tile::Empty, Tile::Empty, Tile::Walkable, Tile::Walkable],
vec![Tile::Walkable, Tile::Walkable, Tile::Empty, Tile::Empty, Tile::Empty, Tile::Empty],
vec![Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable],
vec![Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable]
];
let another = vec![
vec![Tile::Empty, Tile::Empty, Tile::Empty, Tile::Walkable, Tile::Empty, Tile::Empty, Tile::Empty],
vec![Tile::Empty, Tile::Empty, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Empty, Tile::Empty],
vec![Tile::Empty, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Empty],
vec![Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable],
vec![Tile::Walkable, Tile::Walkable, Tile::Empty, Tile::Walkable, Tile::Empty, Tile::Walkable, Tile::Walkable],
vec![Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable],
vec![Tile::Walkable, Tile::Walkable, Tile::Empty, Tile::Walkable, Tile::Empty, Tile::Walkable, Tile::Walkable],
vec![Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable],
vec![Tile::Empty, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Empty],
vec![Tile::Empty, Tile::Empty, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Empty, Tile::Empty],
vec![Tile::Empty, Tile::Empty, Tile::Empty, Tile::Walkable, Tile::Empty, Tile::Empty, Tile::Empty]
];
let rooms = vec![prebuilt, another];
let mut root = Leaf::new(0, 0, self.level.width, self.level.height, 8);
root.generate(rng);
root.create_rooms(rng, &mut rooms.iter());
...
}
...
fn create_rooms<'a, I>(&mut self, rng: &mut StdRng, rooms: &mut I)
where I: Iterator<Item = &'a Vec<Vec<Tile>>> {
if let Some(ref mut room) = self.left_child {
room.as_mut().create_rooms(rng, rooms);
};
if let Some(ref mut room) = self.right_child {
room.as_mut().create_rooms(rng, rooms);
};
let min_room_width = 4;
let min_room_height = 3;
// if last level, add a room
if self.is_leaf() {
let room = rooms.next(); // get next prebuilt room
let width = rng.gen_range(min_room_width, self.width);
let height = rng.gen_range(min_room_height, self.height);
let x = rng.gen_range(0, self.width - width);
let y = rng.gen_range(0, self.height - height);
match room {
// if we have a prebuilt room, use it
Some(prebuilt) => self.room = Some(Room::new(x + self.x, y + self.y, prebuilt[0].len() as i32, prebuilt.len() as i32, Some(prebuilt.clone()))),
// if not, create a rectangular one
None => self.room = Some(Room::new(x + self.x, y + self.y, width, height, None))
};
}
if let (Some(ref mut left), Some(ref mut right)) = (&mut self.left_child, &mut self.right_child) {
create_corridors(rng, left, right);
};
}
...Right, quite a lot has changed here. We're importing Tile from level so we can create prebuilt rooms in place_rooms: the prebuilt rooms, prebuilt and another, are just two-dimensional vectors of tiles, to tie in with the refactoring we did earlier in Room::new. Both of these prebuilt rooms are added to another vector, rooms, then passed into create_rooms.
create_rooms's method signature has had a big overhaul: it now has a lifetime, a trait and a where clause:
fn create_rooms<'a, I>(&mut self, rng: &mut StdRng, rooms: &mut I)
where I: Iterator<Item = &'a Vec<Vec<Tile>>> {The lifetime 'a is needed since we're borrowing the contents of rooms, so we need to specify how long rooms has to last. I is a generic trait, which, along with the where clause, specifies that rooms is going to be an iterator containing a two-dimensional vector of tiles.
where is a completely optional bit of syntax which is used to tidy up method signatures. We could have written create_rooms like this:
fn create_rooms<'a, I: Iterator<Item = &'a Vec<Vec<Tile>>>>(&mut self, rng: &mut StdRng, rooms: &mut I) {but this is quite messy - you have to read half a line before you even get to the parameters! It can get even worse if the generic type has to implement multiple traits, so moving everything into a where clause on a separate line makes things a lot easier to read.
We also added a match to use the next room in the rooms vector, or use an empty one if there are none left:
if self.is_leaf() {
let room = rooms.next(); // get next prebuilt room
let width = rng.gen_range(min_room_width, self.width);
let height = rng.gen_range(min_room_height, self.height);
let x = rng.gen_range(0, self.width - width);
let y = rng.gen_range(0, self.height - height);
match room {
// if we have a prebuilt room, use it
Some(prebuilt) => self.room = Some(Room::new(x + self.x, y + self.y, prebuilt[0].len() as i32, prebuilt.len() as i32, Some(prebuilt.clone()))),
// if not, create a rectangular one
None => self.room = Some(Room::new(x + self.x, y + self.y, width, height, None))
};
}This is a very round-about way of saying that create_rooms just iterates over a vector of prebuilt rooms. It takes the next item from the vector and uses that as the room to add; if there are none left, then it passes None to Room::new to generate a rectangular room like before.
This means that the first room we place will always be the first prebuilt room in our list, and each prebuilt room will only be used once. You could change the selection part in create_rooms to use a randomly-generated number to pick from the rooms vector rather than use rooms.next(), which would mean each prebuilt room could be used multiple times, or change which room gets the prebuilt room. I'll leave this to you to implement.
Run the programme again with cargo run -- -a bsp, and you'll see the prebuilt rooms being used in the level:
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1
1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1Macros
Creating prebuilt rooms is currently very wordy, and looks quite messy:
let prebuilt = vec![
vec![Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable],
vec![Tile::Empty, Tile::Empty, Tile::Empty, Tile::Empty, Tile::Walkable, Tile::Walkable],
vec![Tile::Walkable, Tile::Walkable, Tile::Empty, Tile::Empty, Tile::Empty, Tile::Empty],
vec![Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable],
vec![Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable, Tile::Walkable]
];It'd be nicer if we had a smaller, simpler way of creating a room in code - and luckily, with Rust's macros, we can! This is what we're aiming for:
let lovely_room = room![
[0, 0, 0, 1, 0, 0, 0],
[0, 0, 1, 1, 1, 0, 0],
[0, 1, 1, 1, 1, 1, 0],
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 0, 1, 0, 1, 1],
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 0, 1, 0, 1, 1],
[1, 1, 1, 1, 1, 1, 1],
[0, 1, 1, 1, 1, 1, 0],
[0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 1, 0, 0, 0]
];which is much easier to read than the first version.
Macros have their own syntax in Rust, and can quickly get complicated, so I really encourage you to read the Rust book or the Little Book of Rust Macros to get more information, since I will almost certainly miss something when explaining.
The first thing to do is to create a macro called room! in room.rs:
// room.rs
macro_rules! room {
() => ()
}
...This creates a macro which has no rules, so won't actually do anything, but is a good starting point. We also need to alter main.rs to add the #[macro_use] directive to the room module, otherwise we won't be able to use the room! macro we just defined in other modules of our code.
// main.rs
...
#[macro_use]
mod room;
...Macros in Rust can have multiple rules, and will check each one to see if any match. We need our macro to match square brackets surrounding at least one expression; each expression can have a comma following it (ie [1, 0, 1], and that entire pattern can also be repeated one or more times, ie
[
[1, 0, 1],
[0, 0, 0]
]These are example rules to show increasing complexity as we get towards the final rule - try running these on the Rust Playground to see how they work.
macro_rules! room {
// single expression
( $x:expr ) => (vec![$x]);
// multiple expressions
( $( $x:expr ),* ) => ( vec![$( $x ),*] );
// square brackets containing multiple expressions
( $([ $($x:expr),* ])* ) => ( vec![$( $x ),*] );
// multiple square brackets containing multiple expressions
( $( [ $( $x:expr ),* ] ),*) => ( vec![$( vec![$( $x ),*]),*] );
}
pub fn main() {
let room = room![1];
println!("{:?}", room); // [1]
let another = room![1, 1];
println!("{:?}", another); // [1, 1]
let square = room![ [0, 1] ];
println!("{:?}", square); // [ [0, 1] ]
let fourth = room![ [0, 1, 0], [2, 3, 4], [5, 6, 7] ];
println!("{:?}", fourth); // [ [0, 1, 0], [2, 3, 4], [5, 6, 7] ]
}Single expression macro
Taking these one by one:
( $x:expr ) => (vec![$x]);This will accept a single expression and return the expression wrapped in a vector:
let room = room![1];
println!("{:?}", room);
// => [1]Multiple expression macro
( $( $x:expr ),* ) => ( vec![$( $x ),*] );This rule accepts any number of expressions separated by commas, and returns them wrapped in a single vector:
let another = room![1, 1];
println!("{:?}", another);
// => [1, 1]
let something_else = room![1, 1, 0, 1, 0, 1, 1];
// => [1, 1, 0, 1, 0, 1, 1]Square brackets with multiple expressions
( $([ $($x:expr),* ])* ) => ( vec![$( $x ),*] );This rule accepts square brackets wrapping multiple arguments, similar to a single vector:
let square = room![ [0, 1] ];
println!("{:?}", square);
// => [ [0, 1] ]Multiple square brackets with multiple expressions
( $( [ $( $x:expr ),* ] ),*) => ( vec![$( vec![$( $x ),*]),*] );Finally, this rule accepts mutiple square brackets wrapping mutiple expressions, similar to a two-dimension vector:
let fourth = room![ [0, 1, 0], [2, 3, 4], [5, 6, 7] ];
println!("{:?}", fourth);
// => [ [0, 1, 0], [2, 3, 4], [5, 6, 7] ]Having all of these rules in our macro means we can accept any of the above examples as valid input. If we only wanted to accept two-dimensional vectors, then we'd only keep the last rule.
These rules just repeat out exactly what's passed into them wrapped in a vector, but we need to transform the number into a tile. We can do this by matching on the $x expression:
// room.rs
...
macro_rules! room {
( $x:expr ) => (vec![ match $x {
1 => Tile::Walkable,
_ => Tile::Empty
}]);
}Use the updated macro in bsp.rs:
// bsp.rs
...
fn place_rooms(&mut self, rng: &mut StdRng) {
let prebuilt = room![
[1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 1, 1],
[1, 1, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1]
];
let another = room![
[0, 0, 0, 1, 0, 0, 0],
[0, 0, 1, 1, 1, 0, 0],
[0, 1, 1, 1, 1, 1, 0],
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 0, 1, 0, 1, 1],
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 0, 1, 0, 1, 1],
[1, 1, 1, 1, 1, 1, 1],
[0, 1, 1, 1, 1, 1, 0],
[0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 1, 0, 0, 0]
];
let rooms = vec![prebuilt, another];
...Using the macro makes defining the rooms much more concise and readable; it also means you can define rooms in another file or even another file or format, such as Tiled. Run again with cargo run -- -a bsp, and you should see the same result as before.
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1
1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1