# Handling Big Arrays

Hello,

I’ve been working on the 3pi quite a lot recently. I really like it, but my knowledge and abilities in the coding area are a bit limited.
I’m currently trying to add to the 3pi a program through which he will sort a problem similar to the henoi towers. (Why? I really can’t say currently.)
The code listed below is universal for any number of disks, but when I go up to 4 “disks” the 3pi never finishes the calculations.

Or at least, I never gave him enough time. At the end of my post you can find the code of this current program. with 3 “disks” i’d like to be able to do it with 5. meaning that only two lines need to change.

``````unsigned int array[10080]={0};
unsigned int target[60]={0};``````

The AVR studio simulator alerts of "Stack Overflow"
Is there room enough in the controller to store this array? Where is it being stored (RAM or PROGMEM)? If there is not enough room, is there anyway to “upgrade” the 3pi to one of the new controllers? (I wouldn’t wanna buy and assemble a new robot, seeing as when I buy new parts they have to be shipped overseas)

Other suggestions?
Questions?

``````#include <pololu/3pi.h>
#include <avr/pgmspace.h>

int validate(unsigned int *p, unsigned int a, unsigned int b, unsigned int c,unsigned int x)
{
int i=0;
while(i<=x)
{
if((a==p[i])&(b==p[i+1])&(c==p[i+2]))
{
return 0;
}
i=i+4;
}
return 1;
}

int navigation(unsigned int * p,unsigned int * t)
{
unsigned int x=0;
unsigned int i=0;
unsigned int agent=0;
while((p[0+i] != t[0]) | (p[1+i] != t[1]) | (p[2+i] != t[2]))
{
clear();
print_long(i);
//if branch 1 is not empty
if(p[0+i] != 0)
{
//select the agent about to move;
agent=p[0+i]%10;
//create the state when the new agent moved to branch two.
if(validate(p,p[0+i]/10,p[1+i]*10+agent,p[2+i],x))
{
x=x+4;
p[0+x]=p[0+i]/10;
p[1+x]=p[1+i]*10+agent;
p[2+x]=p[2+i];
//don't forget to list who the father is.
p[3+x]=i;
if((p[0+x] == t[0]) & (p[1+x] == t[1]) & (p[2+x] == t[2]))
{
return(i);
}
}

//create the state when the new agent moved to branch three.
if(validate(p,p[0+i]/10,p[1+i],p[2+i]*10+agent,x))
{
x=x+4;
p[0+x]=p[0+i]/10;
p[1+x]=p[1+i];
p[2+x]=p[2+i]*10+agent;
//don't forget to list who the father is
p[3+x]=i;
if((p[0+x] == t[0]) & (p[1+x] == t[1]) & (p[2+x] == t[2]))
{
return(i);
}
}

}
if(p[1+i] !=0)
{
//select the agent about to move;
agent=p[1+i]%10;
//create the state when the new agent moved to branch one.
if(validate(p,p[0+i]*10+agent,p[1+i]/10,p[2+i],x))
{
x=x+4;
p[0+x]=p[0+i]*10+agent;
p[1+x]=p[1+i]/10;
p[2+x]=p[2+i];
//don't forget to list who the father is.
p[3+x]=i;
if((p[0+x] == t[0]) & (p[1+x] == t[1]) & (p[2+x] == t[2]))
{
return(i);
}
}

//create the state when the new agent moved to branch three.
if(validate(p,p[0+i],p[1+i]/10,p[2+i]*10+agent,x))
{
x=x+4;
p[0+x]=p[0+i];
p[1+x]=p[1+i]/10;
p[2+x]=p[2+i]*10+agent;
//don't forget to list who the father is
p[3+x]=i;
if((p[0+x] == t[0]) & (p[1+x] == t[1]) & (p[2+x] == t[2]))
{
return(i);
}
}
}
if(p[2+i] !=0)
{
//select the agent about to move;
agent=p[2+i]%10;
//create the state when the new agent moved to branch one.
if(validate(p,p[0+i]*10+agent,p[1+i],p[2+i]/10,x))
{
x=x+4;
p[0+x]=p[0+i]*10+agent;
p[1+x]=p[1+i];
p[2+x]=p[2+i]/10;				//don't forget to list who the father is.
p[3+x]=i;
if((p[0+x] == t[0]) & (p[1+x] == t[1]) & (p[2+x] == t[2]))
{
return(i);
}
}

//create the state when the new agent moved to branch two.
if(validate(p,p[0+i],p[1+i]*10+agent,p[2+i]/10,x))
{
x=x+4;
p[0+x]=p[0+i];
p[1+x]=p[1+i]*10+agent;
p[2+x]=p[2+i]/10;
//don't forget to list who the father is
p[3+x]=i;
if((p[0+x] == t[0]) & (p[1+x] == t[1]) & (p[2+x] == t[2]))
{
return(i);
}
}
}
i=i+4;

}
return 0;
}
void create_path(unsigned int *p, unsigned int *t)
{
int i;
int x=0;
while(i!=0)
{
t[3+x*3]=p[i];
t[3+x*3+1]=p[i+1];
t[3+x*3+2]=p[i+2];
i=p[i+3];
x=x+1;
}
t[3+x*3]=p[i];
t[3+x*3+1]=p[i+1];
t[3+x*3+2]=p[i+2];
}

int main()
{
clear();
print_long(bat);
print("mV");
lcd_goto_xy(0,1);
print("Starting");

delay_ms(100);

unsigned int array[240]={0};
unsigned int target[27]={0};
unsigned int *parray;
unsigned int *ptarget;
parray=array;
ptarget=target;
array[0]=123;
array[1]=0;
array[2]=0;
target[0]=321;
target[1]=0;
target[2]=0;

create_path(parray,ptarget);

while(1)
{
clear();
print_long(bat);
print("mV");
lcd_goto_xy(0,1);
delay_ms(1000);
}

return 0;
}``````

Hello.

Your arrays are being stored in RAM (flash is really only useful for storing constants known at compile time, like strings of text or the notes of a song), and the 3pi only has 2 KB of RAM, so you are definitely exceeding that when you try to allocate a 20,000-byte arary. The reason your are getting a stack overflow is because the ATmega328 stack is also stored in RAM, so you have to make sure that your data usage leaves enough room for the stack.

It sounds like you might benefit from offloading this task to a much more capable microcontroller (e.g. an mbed), or you can consider adding some serial SRAM modules to your 3pi. Another approach would be to offload the task to a PC and use a pair of wireless serial modules to communicate the answer back to the 3pi, but maybe that isn’t as interesting?

Another approach is to consider whether you can be more clever with your algorithm and handle your data in smaller chunks. Do you really need to store 10080 integers or can you get by with a series of computations on smaller arrays? Does your array really need to consist of integers (2-byte values: -32768 to 32767) or can you get by with chars (1-byte values: -128 to 127)? And if you don’t even need a full byte for your array element, you could use each array element to store multiple values.

- Ben

Hey Ben,
Thanks for the speedy replay

This sounds like the most reasonable solution, but I don’t want to start messing with the hardware too much. Are there any modules like these out there (with possibly the same awesome line following the 3pi has? I know I’m asking for much… but… this is very handy for me.)
Is there someone in Pololu I can make contact with if I’d want to order custom made modules?

I tried minimizing it before, right now every integer stores a number of maximum 5 digits. And I can do with 360 integers, but with a maximum value of 9954321.
I’m not so sure, which one of these will be smaller. According to my calculations, 10080 integers is the minimum size of the array.

Once again, the first part is the better solution so I might expand my simulations even further. A contact mail would be handy.

EDIT: I just noticed you guys have the new modded m3pi, looks awesome. But I’m a little worried about the AAA batteries. I intend to work with 5-9 of these here in the lab and charging 20-36 AAA batteries is a little over the top for me. What are my alternatives here? Use an external charger straight into the m3pi?

Thanks a lot,
Uriel

You can contact us directly about custom engineering, but I think going with an mbed-controlled m3pi robot is a much better alternative. You can use an external battery charger to charge the m3pi batteries via its charge port (the same way you can recharge the 3pi batteries through the 3pi’s charge port). We have information about recharging the 3pi batteries in the 3pi FAQ, and this information applies equally to the m3pi.

- Ben