Member Avatar for fulyaoner

Hi to everyone...
I am told to code a Schelling's Segregation Model simulation in C++ . This is about agent simulation and let me explain shortly what it is wanted:

* There is a place like the chessboard (8*8)
* there are 2 kind of people , the X and the O
* place randomly 20 X and 20 O , with no overlapping.
* there is no runaway from the board. (i mean, at the end, still will be 40 people and 24 empty cells.
* Then you should move someone to somewhere randomly, that at least there will be 3 agents with the same type (x or O).
* I mean, a agent will be happy if it has at least 2 neighnours. else, it will change its position till it can found a place with at least 2 other neighbours.
* the program will just run and print to a file.

I coded nearly all the needed things, but confused what to do next when i come to deciding of the moving process.

Now, I look at the [0][0] th cell, if there is an agent there, then I look to its neighbours. just like Linked lists, a data called m_pNext is used in the class of agent. It will mimic like list, and will show its next agent. I set something to next, but i dont know how i will decide this for all of the agents.

plz give me a way about this confusion. Which way can be the sortest?
I run this code in mingw developer studio, known as a g++ compiler.

code is attached, and one result text file.

Thanks

Random places 
 0  1  2  3  4  5  6  7
_________________________________
 X  O  -  -  -  O  -  O 
 O  X  X  O  -  O  -  - 
 X  O  X  O  X  -  X  O 
 O  X  X  O  -  X  -  - 
 X  O  X  O  -  -  -  X 
 -  -  O  O  X  -  O  X 
 -  -  X  O  -  X  O  O 
 O  X  -  -  X  -  -  X 

_________________________________
after simulation 
0-0 and 1--1 right-down ngh  1
0-2 and 0--3 right side ngh  0
0-3 and 0--4 right side ngh  0
0-4 and 1--4 down side ngh 0
0-5 and 1--5 down side ngh 2
0-6 and 1--6 down side ngh 0
0-7 and 0--8 right side ngh  2
1-0 and 2--1 right-down ngh  2
1-1 and 1--2 right side ngh  1
1-2 and 2--2 down side ngh 1
1-3 and 2--3 down side ngh 2
1-4 and 2--5 right-down ngh  0
1-6 and 1--7 right side ngh  0
2-0 and 3--1 right-down ngh  1
2-2 and 3--2 down side ngh 1
2-3 and 3--3 down side ngh 2
2-4 and 3--5 right-down ngh  1
2-5 and 3--6 right-down ngh  0
2-7 and 2--8 right side ngh  2
3-0 and 4--1 right-down ngh  2
3-1 and 3--2 right side ngh  1
3-2 and 4--2 down side ngh 1
3-3 and 4--3 down side ngh 2
3-4 and 4--4 down side ngh 0
3-6 and 3--7 right side ngh  0
3-7 and 4--8 right-down ngh  0
4-1 and 5--2 right-down ngh  2
4-3 and 5--3 down side ngh 2
4-4 and 4--5 right side ngh  0
4-5 and 4--6 right side ngh  0
4-7 and 5--7 down side ngh 1
5-0 and 5--1 right side ngh  0
5-1 and 6--1 down side ngh 0
5-2 and 5--3 right side ngh  2
5-3 and 6--3 down side ngh 2
5-4 and 6--5 right-down ngh  1
5-6 and 6--6 down side ngh 2
6-0 and 6--1 right side ngh  0
6-1 and 7--2 right-down ngh  0
6-4 and 7--5 right-down ngh  0
6-6 and 6--7 right side ngh  2
6-7 and 6--8 right side ngh  2
7-2 and 7--3 right side ngh  0
7-5 and 7--6 right side ngh  0
7-7 and 8--8 right-down ngh  1

_________________________________
1 0-0
1 1-1
1 1-2
1 2-2
1 3-2
#include <iostream.h>
#include <time.h>
#include <stdlib.h>
#include <math.h>
#include <fstream.h>


ofstream a_file("sample.txt");

//declaration of public variables

const int pop=100;

class agent { //declaration of class name.
	agent *m_pNext;
public:
	int m_x, m_y;
	int m_type; /* 1 = X  , 2 = O*/
	int m_nCount;
 	
	agent(int type);   
	agent(void);
	
	void point_to_next(agent *where_to_point);
	agent *get_next(void);
	
	int get_x(void);
	int get_y(void);
	void set_x(int);
	void set_y(int);
	int get_type(void);
	int get_nCount();
	void increaseCount();
};

agent::agent(void)
{
	m_x = -1;
	m_y = -1;
	m_nCount = -1;
}

agent::agent(int type) {       //defining the constructor function
	
	m_pNext = NULL;
	m_type = type;
	m_x = -1;
	m_y = -1;
	m_nCount = -1;
}
int agent::get_nCount()
{
	return m_nCount;
}
	
void agent::increaseCount()
{
	m_nCount++;
}

int agent::get_x(void)
{
	return m_x;
}
int agent::get_y(void)
{
	return m_y;
}
void agent::set_x(int x)
{
	m_x = x;
}
void agent::set_y(int y)
{
	m_y = y;
}
int agent::get_type(void)
{
	return m_type;
}


void agent::point_to_next(agent *where_to_point) 
{
	m_pNext = where_to_point;
}
agent *agent::get_next(void) 
{ 
	return m_pNext; 
}

 
class board {
public:
	agent livingPlace[8][8];
	
	board(void);
	void PrintBoard();
	void MakeThemHappy();
	void PrintLinkedAgents();
private:
	void SetRandomPlaceForXs();
	void SetRandomPlaceForOs();
	
};

board::board(void)
{
	//cout << "board created..." << endl;
	
	// first initlialize all to 0 - empty
	for (int i = 0; i < 8; i++)
	{
		for (int j = 0; j < 8; j++)
		{
			agent temp(0);
			livingPlace[i][j] = temp;
		}
	}
	
	SetRandomPlaceForXs();
	SetRandomPlaceForOs();
	
}


void board::SetRandomPlaceForXs()
{
	//cout<< "setting random places for 20 x agents " << endl << endl;
	
	int i = 0, x, y;
	agent *aX;
	
	for (i = 0; i < 20; i++)
	{
		do
		{
			aX = new agent(1);
			
			x = rand() % 8;
			y = rand() % 8;
				
			aX->set_x(x);
			aX->set_y(y);
		}while(livingPlace[x][y].get_x() != -1);
		
		livingPlace[x][y] = *aX;
		
	}
	
}
	

void board::SetRandomPlaceForOs()
{
	//cout<< "setting random places for 20 O agents " << endl  << endl;
	 
	int i = 0,  x, y;
	agent *aO;
	
	for (i = 0; i < 20; i++)
	{
		do
		{
			aO = new agent(2);
			
			x = rand() % 8;
			y = rand() % 8;
				
			aO->set_x(x);
			aO->set_y(y);
		}while(livingPlace[x][y].get_x() != -1);
		
		livingPlace[x][y] = *aO;
		
	}
	
}


void board::PrintBoard()
{
	int i, j;
	for (i = 0; i < 8; i++)
	{
		for (j = 0; j < 8; j++)
		{
			if (livingPlace[i][j].get_x() != -1)
			{
				if (livingPlace[i][j].get_type() == 1)
					a_file << " X " ;
				else
					a_file << " O ";
			}
			else
				a_file << " - " ;
		}
		a_file << endl;
	}
}






void board::MakeThemHappy()
{
	// first, lets look at their randomly places happines values, and link them 
	// to each other if they are already happy neighbour
	
	int i, j, type;
	for (i = 0; i < 8; i++)
	{
		for (j = 0; j < 8; j++)
		{
			type = livingPlace[i][j].get_type();
			if (type == livingPlace[i][j+1].get_type())
			{
				a_file << i << "-" << j << " and " << i << "--" << j + 1 << " right side ngh  " << type << endl;
				livingPlace[i][j].point_to_next(&livingPlace[i][j+1]);
			}
			else if (type == livingPlace[i+1][j].get_type())
			{
				a_file << i << "-" << j << " and " << i + 1 << "--" << j  << " down side ngh " << type << endl;
				livingPlace[i][j].point_to_next(&livingPlace[i+1][j]);
			}	
			else if (type == livingPlace[i+1][j+1].get_type())
			{
				a_file << i << "-" << j << " and " << i + 1 << "--" << j+1  << " right-down ngh  " << type << endl;
				livingPlace[i][j].point_to_next(&livingPlace[i+1][j+1]);
			}	
		}
	}
}

void board::PrintLinkedAgents()
{
	if (livingPlace[0][0].get_type() != 0)
	{
		agent *temp;
		
		temp = &livingPlace[0][0];
		while ( temp->get_next()  != NULL)
		{
			a_file << temp->get_type() << " " << temp->get_x() << "-" << temp->get_y() << endl;
			
			temp = temp->get_next();
		}
	}
}
int main() 
{
	srand(time(NULL));
	
	board myBoard;
	
	a_file << "Random places " << endl ;
	a_file << " 0  1  2  3  4  5  6  7" << endl;
	a_file << "_________________________________" << endl;
	
	myBoard.PrintBoard();
	a_file << endl;
	a_file << "_________________________________" << endl;
	
	a_file << "after simulation " << endl;
	myBoard.MakeThemHappy();
	
	a_file << endl;
	a_file << "_________________________________" << endl;
	
	myBoard.PrintLinkedAgents();
  
	system("pause");
	return 0;
}
  • 2 Contributors
  • 2 Replies
  • 496 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by fulyaoner

Dani AI

Generated

A practical way to keep your linked-list agent structure (m_pNext) while making moves simple and fast is to use the list for iteration and an auxiliary occupancy array for neighbor checks. That keeps you faithful to the assignment () while avoiding the performance pain of searching the whole list for every neighbor (the point was hinting at). The occupancy array is just a small 8x8 map of pointers or chars that you update whenever an agent moves.

# build occupancy from linked list
for(node = head; node; node = node->m_pNext) board[node.r][node.c] = node

# main loop
repeat until no unhappy agents or max_iters:
  unhappy = []
  for(node = head; node; node = node->m_pNext)
    if(countSameNeighbors(board,node.r,node.c) < 2) {
      unhappy.push_back(node)
      empty_cells.push_back((node.r,node.c))   # mark old spot empty for this round
    }

  shuffle(empty_cells)
  for(node in unhappy)
    target = findFirst(empty_cells, t -> wouldBeHappy(board,t,node.type))
    if(target) {
      board[node.r][node.c] = null
      node.r,node.c = target
      board[target] = node
      remove target from empty_cells
    }

Implementation tips: do moves in this two-phase style (collect unhappy, then move) to avoid order-dependency. Use a shuffled empty_cells vector or sample a fixed number of random empties per agent to avoid O(N^2) behavior. Set sensible caps (max tries per agent, max iterations overall) so the simulation terminates. When using the linked list, only change node position fields and the occupancy array — don’t rewire m_pNext unless you really need to insert/delete nodes.

Common bugs to watch for: off-by-one neighbor loops (stay inside 0..7), forgetting to clear an old cell in the occupancy array, failing to remove a chosen empty from the pool, and RNG not being seeded. Log a few board snapshots (or counts of unhappy agents) each iteration to verify progress.

Recommended Answers

All 2 Replies

Member Avatar for Member #46692

Looks like the game of life, of some sort. Personally, I'd say you're over complicating this with linked list.

Basic arrays is all you need.

Member Avatar for fulyaoner

Looks like the game of life, of some sort. Personally, I'd say you're over complicating this with linked list.

Basic arrays is all you need.

sure an array is enouhg but, this is what is wanted.

Thanks

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.